Neural network accuracy for simple classification
I will add my 2 cents at the end of this answer. However, this is how it can be done using a neural network. Firstly, yes, you should expect to need more data to train even a simple neural network because their are more parameters that need tuning. Think of them like little faucets that you need to tune in order to get the right output volume based on an input. If you have millions of these faucets you an imagine that this is an arduous process. 

You will need some of the following imports

from __future__ import print_function
import keras
from keras.datasets import mnist
from keras.models import Sequential
from keras.layers import Dense, Dropout, Flatten
from keras.layers import Conv2D, MaxPooling2D
from keras.callbacks import ModelCheckpoint
from keras.models import model_from_json
from keras import backend as K


But, in your case you know what your data should be so you can simulate it. I do this as follows and make a training and testing set. 

import numpy as np

n = 10
m = 2

x_train = np.zeros((n, m))
y_train = np.zeros((n,))
for i in range(n):
    label = np.random.randint(0,m)
    y_train[i] = label
    x_train[i, label] = 1

x_test = np.zeros((n//3, m))
y_test = np.zeros((n//3,))
for i in range(n//3):
    label = np.random.randint(0,m)
    y_test[i] = label
    x_test[i, label] = 1


Now we will have a training set which contains $n$ instances and a testing set with a third as many. $m$ is the number of possible inputs. For cat vs. dog this would be $m=2$. You will be using your more general case where $m=10$. Each entry in the matrix $x$ has the vector with one-hot encoded vector where the index in accordance with the label is 1.

We need to reshape the data for it to fit with the Keras structure.

# The known number of output classes.
num_classes = m

# Channels go last for TensorFlow backend
x_train_reshaped = x_train.reshape(x_train.shape[0], m,)
x_test_reshaped = x_test.reshape(x_test.shape[0], m,)
input_shape = (m,)

# Convert class vectors to binary class matrices. This uses 1 hot encoding.
y_train_binary = keras.utils.to_categorical(y_train, num_classes)
y_test_binary = keras.utils.to_categorical(y_test, num_classes)


We then build our model

model = Sequential()
model.add(Dense(64, activation='relu', input_shape = input_shape))
model.add(Dense(num_classes, activation='softmax'))

model.compile(loss=keras.losses.categorical_crossentropy,
              optimizer=keras.optimizers.Adadelta(),
              metrics=['accuracy'])


We then train our model

epochs = 4
batch_size = 128
# Fit the model weights.
history = model.fit(x_train_reshaped, y_train_binary,
          batch_size=batch_size,
          epochs=epochs,
          verbose=1,
          validation_data=(x_test_reshaped, y_test_binary))



  Epoch 4/4 10/10 [==============================] - 0s 251us/step -
  loss: 0.6247 - acc: 0.6000 - val_loss: 0.5311 - val_acc: 1.0000


Voila, now you have perfect classification with this network. You can play around with the model and see a summary of the model using.

model.summary()




For $m = 10$

Due to the higher complexity that this set has you will need to increase the number of instances in your training set. I will also 2 layers to our model and make them less wide. Furthermore, we will add more epochs so we will train longer.

import numpy as np

n = 1000
m = 10

x_train = np.zeros((n, m))
y_train = np.zeros((n,))
for i in range(n):
    label = np.random.randint(0,m)
    y_train[i] = label
    x_train[i, label] = 1

x_test = np.zeros((n//3, m))
y_test = np.zeros((n//3,))
for i in range(n//3):
    label = np.random.randint(0,m)
    y_test[i] = label
    x_test[i, label] = 1

# The known number of output classes.
num_classes = m

# Channels go last for TensorFlow backend
x_train_reshaped = x_train.reshape(x_train.shape[0], m,)
x_test_reshaped = x_test.reshape(x_test.shape[0], m,)

input_shape = (m,)

# Convert class vectors to binary class matrices. This uses 1 hot encoding.
y_train_binary = keras.utils.to_categorical(y_train, num_classes)
y_test_binary = keras.utils.to_categorical(y_test, num_classes)

model = Sequential()
model.add(Dense(32, activation='relu', input_shape = input_shape))
model.add(Dense(32, activation='relu'))
model.add(Dense(num_classes, activation='softmax'))

model.compile(loss=keras.losses.categorical_crossentropy,
              optimizer=keras.optimizers.Adadelta(),
              metrics=['accuracy'])

epochs = 10
batch_size = 128
# Fit the model weights.
history = model.fit(x_train_reshaped, y_train_binary,
          batch_size=batch_size,
          epochs=epochs,
          verbose=1,
          validation_data=(x_test_reshaped, y_test_binary))



  Epoch 10/10 1000/1000 [==============================] - 0s 49us/step
  - loss: 1.5977 - acc: 1.0000 - val_loss: 1.5235 - val_acc: 1.0000




My suggestions

I would not use a NN for such a case. Most of the frameworks allow you to add information throughout your model. Such that if you have images you can run a CNN over them, then when you are ready to convert your layers to a densely connected layer you can in additional information, such as vectorized text. 

You can thus use a random forests approach or something even simpler to get your 100% classification even faster. Then you can feed the output of this model to your deep learning framework which has already "extracted the features" from the images and concatenate these additional features to that tensor. Then you will pass this larger tensor through the subsequent Dense layers to get your final output.