How to calculate minimum excludant from graph for different permutation?

Question

This is practice problem in codechef. For complete question

What I have done so far is, created a graph from list of tuples

(Ex: input_list = [(1,2),(2,3)])

And taken all permutations for the set of input_list. Need to calculate MEX of each permutation and calculate length of distinct return values of mex() function.

# https://www.codechef.com/problems/TREEMX


from collections import defaultdict
from itertools import permutations


class Graph:
    """ Graph is data structure(directed). """


    def __init__(self, connections):
        """ Initializing graph with set as default value. """
        self._graph = defaultdict(set)
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections(list of tupules) to graph. """
        for node1, node2 in connections:
            self.add(node1,node2)

    def add(self, node1, node2):
        """ Add node1 and node2 to graph which is initialized with set by default. """
        self._graph[node1].add(node2)
        self._graph[node2].add(node1)

    def get_graph(self):
        return dict(self._graph)


def mex(arr_set):
    mex = 0
    while mex in arr_set:
        mex+=1
    return mex


def process(graph, order):
    a_p = [0] * len(order)
    for i, el in zip(range(len(order)), order):
        a_p[i] = mex(graph[el])
    return a_p


t = int(input())
for _ in range(t):
    v = int(input())
    e = []
    for i in range(v-1):
        e.append(tuple(map(int, input().split())))

    g = Graph(e)
    print(g.get_graph())
    all_vertices = {s for i in e for s in i}
    result = []
    for p in permutations(all_vertices, v):
        out = process(g.get_graph(), p)
        print("{} --> {}".format(p, out))
        result.append(out) if out not in result else None

    print(len(result))

I'm struck at calculating in MEX.

Please explain how to complete that mex function (Please tell how to approach or algorithm to implement that).

Any suggestion to my improve my code are welcome.

Rules of problem:

You have a tree $T$ with $n$ vertices. Consider an ordering $P=(v_1,…,v_n)$ of vertices of $T$. We construct a sequence $A(P)=(a_1,…,a_n)$ using the following process:

• Set all $a_i=−1$.

• Process vertices in order $v_1,…,v_n$. For the current vertex vi set $a_i=MEX(a_{u_1},…,a_{u_k})$, where $u_1,…,u_k$ is the set of neighbours of $v_i$.

Unexpected results:

1
3
1 2
2 3
{1: {2}, 2: {1, 3}, 3: {2}}
(1, 2, 3) --> [0, 0, 0] # should be (0, 1, 0)
(1, 3, 2) --> [0, 0, 0]
(2, 1, 3) --> [0, 0, 0]
(2, 3, 1) --> [0, 0, 0] # should be (1, 0, 1)
(3, 1, 2) --> [0, 0, 0]
(3, 2, 1) --> [0, 0, 0]
1