A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.
Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.
During each player's turn, they must travel along one edge of the graph that meets where they are.  For example, if the Mouse is at node 1, it must travel to any node in graph[1].
Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)
Then, the game can end in 3 ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.
 



Example 1:
Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Explanation:
4---3---1
|   |
2---5
 \ /
  0

 
Note:

3 <= graph.length <= 50
It is guaranteed that graph[1] is non-empty.
It is guaranteed that graph[2] contains a non-zero element.

Difficulty: interview

Starter code:

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (mouse, cat, turn) ?
        def parents(mouse, cat, turn):
            prev_turn = 3 - turn
            if prev_turn == MOUSE: 
                for m2 in graph[mouse]:
                    yield m2, cat, prev_turn
            else:
                for c2 in graph[cat]:
                    if c2:
                        yield mouse, c2, prev_turn

        DRAW, MOUSE, CAT = 0, 1, 2
        colors = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for mouse in range(N):
            for cat in range(N):
                degree[mouse, cat, MOUSE] = len(graph[mouse])
                degree[mouse, cat, CAT] = len(graph[cat]) - (0 in graph[cat])  # cat can not be at hole 0

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for cat in range(N):
            for turn in [MOUSE, CAT]:
                # color MOUSE for all node with mouse=0
                mouse = 0
                colors[mouse, cat, turn] = MOUSE
                queue.append((mouse, cat, turn, MOUSE))
                # color CAT for all node with mouse = cat !=0, cat can not be at hole 0
                if cat > 0:
                    mouse = cat
                    colors[mouse, cat, turn] = CAT
                    queue.append((mouse, cat, turn, CAT))

        # percolate
        while queue:
            mouse, cat, turn, color = queue.popleft()
            for prev_mouse, prev_cat, prev_turn in parents(mouse, cat, turn):
                # if this parent is not colored :
                if colors[prev_mouse, prev_cat, prev_turn] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if prev_turn == color: # winning move
                        colors[prev_mouse, prev_cat, prev_turn] = color
                        queue.append((prev_mouse, prev_cat, prev_turn, color))
                        if prev_mouse == 1 and prev_cat == 2 and prev_turn == MOUSE: 
                            return color
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[prev_mouse, prev_cat, prev_turn] -= 1
                        if degree[prev_mouse, prev_cat, prev_turn] == 0:
                            colors[prev_mouse, prev_cat, prev_turn] = 3 - prev_turn
                            queue.append((prev_mouse, prev_cat, prev_turn, 3 - prev_turn))
                            if prev_mouse == 1 and prev_cat == 2 and prev_turn == MOUSE: 
                                return color

        return colors[1, 2, 1] # mouse at 1, cat at 2, MOUSE turn

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # For n nodes, the possible longest path in the graph is n. If the cat can win, 
        # its distance to the mouse should decrease, after decease n times if still doesn't 
        # catch the mouse, and mouse haven't reach node 0 yet, means this is a draw
        
        # it takes at most n for mouse to get to 0. At 2*n time, it means mouse take a 
        # detour of at least n steps. It means that there should be at least a loop(size n) 
        # or multiple loops of (size < n).
        
        n = len(graph)
        @lru_cache(None)
        def move(cat, mouse, t):
            # should be 2n but 0.8n also passes all tests
            if t > int(0.8 * n):
                return 0
            elif mouse == 0:
                return 1
            elif cat == mouse:
                return 2
            if t % 2 == 0:
                best_result = 2
                for pos in graph[mouse]:
                    result = move(cat, pos, t + 1)
                    if result == 1:
                        return 1
                    if result == 0:
                        best_result = 0
            else:
                best_result = 1
                for pos in graph[cat]:
                    if pos == 0:
                        continue
                    result = move(pos, mouse, t + 1)
                    if result == 2:
                        return 2
                    if result == 0:
                        best_result = 0
            return best_result
        return move(2, 1, 0)
        
        
        
#         n = len(graph)
#         cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
#         def move(cat, mouse, t):
#             if t == 2 * n:
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if cache[cat][mouse][t] == -1:
#                 mouse_move = (t % 2) == 0
#                 if mouse_move:
#                     best_result = 2
#                     for pos in graph[mouse]:
#                         result = move(cat, pos, t + 1)
#                         if result == 1:
#                             cache[cat][mouse][t] = 1
#                             return 1
#                         if result == 0:
#                             best_result = 0
#                 else:
#                     best_result = 1
#                     for pos in graph[cat]:
#                         if pos == 0:
#                             continue
#                         result = move(pos, mouse, t + 1)
#                         if result == 2:
#                             cache[cat][mouse][t] = 2
#                             return 2
#                         if result == 0:
#                             best_result = 0
#                 cache[cat][mouse][t] = best_result
#             return cache[cat][mouse][t]
#         return move(2, 1, 0)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # For n nodes, the possible longest path in the graph is n. If the cat can win, 
        # its distance to the mouse should decrease, after decease n times if still doesn't 
        # catch the mouse, and mouse haven't reach node 0 yet, means this is a draw
        
        # it takes at most n for mouse to get to 0. At 2*n time, it means mouse take a 
        # detour of at least n steps. It means that there should be at least a loop(size n) 
        # or multiple loops of (size < n).
        
        n = len(graph)
        @lru_cache(None)
        def move(cat, mouse, t):
            if t == n:
                return 0
            elif mouse == 0:
                return 1
            elif cat == mouse:
                return 2
            if t % 2 == 0:
                best_result = 2
                for pos in graph[mouse]:
                    result = move(cat, pos, t + 1)
                    if result == 1:
                        return 1
                    if result == 0:
                        best_result = 0
            else:
                best_result = 1
                for pos in graph[cat]:
                    if pos == 0:
                        continue
                    result = move(pos, mouse, t + 1)
                    if result == 2:
                        return 2
                    if result == 0:
                        best_result = 0
            return best_result
        return move(2, 1, 0)
        
        
        
#         n = len(graph)
#         cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
#         def move(cat, mouse, t):
#             if t == 2 * n:
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if cache[cat][mouse][t] == -1:
#                 mouse_move = (t % 2) == 0
#                 if mouse_move:
#                     best_result = 2
#                     for pos in graph[mouse]:
#                         result = move(cat, pos, t + 1)
#                         if result == 1:
#                             cache[cat][mouse][t] = 1
#                             return 1
#                         if result == 0:
#                             best_result = 0
#                 else:
#                     best_result = 1
#                     for pos in graph[cat]:
#                         if pos == 0:
#                             continue
#                         result = move(pos, mouse, t + 1)
#                         if result == 2:
#                             cache[cat][mouse][t] = 2
#                             return 2
#                         if result == 0:
#                             best_result = 0
#                 cache[cat][mouse][t] = best_result
#             return cache[cat][mouse][t]
#         return move(2, 1, 0)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = 0
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                n = max(n, graph[i][j])
        
        status = [[[0] * 3 for i in range(n + 1)] for j in range(n + 1)] # s[m][c][t]
        
        queue = []
        for i in range(1, n + 1):
            status[i][i][1] = 2
            status[i][i][2] = 2
            status[0][i][1] = 1
            status[0][i][2] = 1
            queue.append((i, i, 1))
            queue.append((i, i, 2))
            queue.append((0, i, 1))
            queue.append((0, i, 2))
        
        while queue:
            next_queue = []
            for element in queue:
                mouse = element[0]
                cat = element[1]
                turn = element[2]
                if turn == 1:
                    for cat_pre in graph[cat]:
                        if cat_pre == 0:
                            continue
                        if status[mouse][cat_pre][2] == 0:
                            status[mouse][cat_pre][2] = 1
                            for cat_alt in graph[cat_pre]:
                                if cat_alt == 0:
                                    continue
                                if status[mouse][cat_alt][1] == 2:
                                    status[mouse][cat_pre][2] = 2
                                    break
                                elif status[mouse][cat_alt][1] == 0:
                                    status[mouse][cat_pre][2] = 0
                            if status[mouse][cat_pre][2] > 0:
                                next_queue.append((mouse, cat_pre, 2))
                else:
                    for mouse_pre in graph[mouse]:
                        if status[mouse_pre][cat][1] == 0:
                            status[mouse_pre][cat][1] = 2
                            for mouse_alt in graph[mouse_pre]:
                                if status[mouse_alt][cat][2] == 1:
                                    status[mouse_pre][cat][1] = 1
                                    break
                                elif status[mouse_alt][cat][2] == 0:
                                    status[mouse_pre][cat][1] = 0
                            if status[mouse_pre][cat][1] > 0:
                                next_queue.append((mouse_pre, cat, 1))
            queue = next_queue
        
        return status[1][2][1]
                        
                            
                            
                        
                        
                    
            
        
        


class Solution:
    def catMouseGame(self, graph):
        CAT, MOUSE, n = 2, 1, len(graph)
        queue = []          # (cat, mouse, turn, winner)
        result = {}
        for i in range(n):
            for j in range(2):
                queue.append((i, 0, j, 1))
                result[(i, 0, j)] = 1
                if i > 0:
                    queue.append((i, i, j, 2))
                    result[(i, i, j)] = 2
                    queue.append((0, i, j, 1))
                    result[(0, i, j)] = 1

        cnt = {}
        for i in range(n):
            for j in range(n):
                cnt[(i, j, 0)] = len(graph[j])
                cnt[(i, j, 1)] = len(graph[i])

        while queue:
            cat, mouse, turn, winner = queue.pop()
            if turn == 1:   # cat move for next step, mouse move for last step
                if winner == 1:
                    for next_step in graph[mouse]:
                        if (cat, next_step, 1 - turn) not in result:
                            result[(cat, next_step, 1 - turn)] = winner
                            queue.append((cat, next_step, 1 - turn, winner))
                else:
                    for next_step in graph[mouse]:
                        if (cat, next_step, 1 - turn) not in result:
                            cnt[(cat, next_step, 1 - turn)] -= 1
                            if cnt[(cat, next_step, 1 - turn)] == 0:
                                result[(cat, next_step, 1 - turn)] = winner
                                queue.append((cat, next_step, 1 - turn, winner))
            else:
                if winner == 2:
                    for next_step in graph[cat]:
                        if next_step == 0:
                            continue
                        if (next_step, mouse, 1 - turn) not in result:
                            result[(next_step, mouse, 1 - turn)] = winner
                            queue.append((next_step, mouse, 1 - turn, winner))
                else:
                    for next_step in graph[cat]:
                        if next_step == 0:
                            continue
                        if (next_step, mouse, 1 - turn) not in result:
                            cnt[(next_step, mouse, 1 - turn)] -= 1
                            if cnt[(next_step, mouse, 1 - turn)] == 0:
                                result[(next_step, mouse, 1 - turn)] = winner
                                queue.append((next_step, mouse, 1 - turn, winner))
        if (2, 1, 0) in result:
            return result[(2, 1, 0)]
        return 0



class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # state: [M=0/C=1, Mpos, Cpos]
        # result: 0-draw, 1-mouse win, 2-cat win

        cache = {}
        def dfs(s, visited):
            if s in cache:
                return cache[s]
            visited.add(s)
            if s[0] == 0:
                ret = dfs_m(s, visited)
            else:
                ret = dfs_c(s, visited)
            visited.remove(s)
            cache[s] = ret
            return ret

        def sorted_neighbor(node, dest):
            nbs = sorted([(n, dist_mat[n][dest]) for n in graph[node]], key=lambda x: x[1])
            return [t[0] for t in nbs]
            
        def dfs_m(s, visited):
            if 0 in graph[s[1]]:
                return 1 # mouse-win

            cat_nbs = set([x for x in graph[s[2]] if x != 0])
            nbs = sorted_neighbor(s[1], 0)
            hold_move = 0
            for node in nbs:
                if node == s[2] or node in cat_nbs: # mouse-lose
                    continue

                s2 = (1, node, s[2])
                if s2 in visited:
                    hold_move += 1
                    continue

                ret = dfs(s2, visited)
                if ret == 1:
                    return 1 # mouse-win
                if ret == 0:
                    hold_move += 1

            if hold_move: 
                return 0 # draw
            else:
                return 2 # cat-win
        
        def dfs_c(s, visited):
            if s[1] in graph[s[2]]:
                return 2 # cat-win

            nbs = sorted_neighbor(s[2], s[1])
            hold_move = 0
            for node in nbs:
                if node == 0:
                    continue

                s2 = (0, s[1], node)
                if s2 in visited:
                    hold_move += 1
                    continue
                ret = dfs(s2, visited)
                if ret == 2:
                    return 2 # cat-win
                if ret == 0:
                    hold_move += 1

            if hold_move:
                return 0 # draw
            else:
                return 1 # mouse-win

        INF_DIST = float('inf')

        def floyd_dist_modified():
            N = len(graph)
            Mat = [[float('inf')] * N for _ in range(N)]
            for i in range(N):
                Mat[i][i] = 0
                for n in graph[i]:
                    Mat[i][n] = 1

            for k in range(1, N):
                for i in range(1, N):
                    for j in range(1, N):
                        Mat[i][j] = min(Mat[i][j], Mat[i][k] + Mat[k][j])

            for n in graph[0]:
                for i in range(1, N):
                    Mat[0][i] = min(Mat[0][i], Mat[0][n] + Mat[n][i])
                    Mat[i][0] = Mat[0][i]

            return Mat
        
        dist_mat = floyd_dist_modified()
        visited = set()
        return dfs((0, 1, 2), visited)


class Solution(object):
    def catMouseGame(self, graph):
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (m, c, t) ?
        def parents(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 3-t
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 3-t

        DRAW, MOUSE, CAT = 0, 1, 2
        color = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m,c,1] = len(graph[m])
                degree[m,c,2] = len(graph[c]) - (0 in graph[c])

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                queue.append((0, i, t, MOUSE))
                if i > 0:
                    color[i, i, t] = CAT
                    queue.append((i, i, t, CAT))

        # percolate
        while queue:
            # for nodes that are colored :
            i, j, t, c = queue.popleft()
            # for every parent of this node i, j, t :
            for i2, j2, t2 in parents(i, j, t):
                # if this parent is not colored :
                if color[i2, j2, t2] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if t2 == c: # winning move
                        color[i2, j2, t2] = c
                        queue.append((i2, j2, t2, c))
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[i2, j2, t2] -= 1
                        if degree[i2, j2, t2] == 0:
                            color[i2, j2, t2] = 3 - t2
                            queue.append((i2, j2, t2, 3 - t2))

        return color[1, 2, 1]

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (m, c, t) ?
        def parents(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 3-t
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 3-t

        DRAW, MOUSE, CAT = 0, 1, 2
        color = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m,c,1] = len(graph[m])
                degree[m,c,2] = len(graph[c]) - (0 in graph[c])

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                queue.append((0, i, t, MOUSE))
                if i > 0:
                    color[i, i, t] = CAT
                    queue.append((i, i, t, CAT))

        # percolate
        while queue:
            # for nodes that are colored :
            i, j, t, c = queue.popleft()
            # for every parent of this node i, j, t :
            for i2, j2, t2 in parents(i, j, t):
                # if this parent is not colored :
                if color[i2, j2, t2] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if t2 == c: # winning move
                        color[i2, j2, t2] = c
                        queue.append((i2, j2, t2, c))
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[i2, j2, t2] -= 1
                        if degree[i2, j2, t2] == 0:
                            color[i2, j2, t2] = 3 - t2
                            queue.append((i2, j2, t2, 3 - t2))

        return color[1, 2, 1]

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (m, c, t) ?
        def parents(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 3 - t
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 3 - t

        DRAW, MOUSE, CAT = 0, 1, 2
        color = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m, c, 1] = len(graph[m])
                degree[m, c, 2] = len(graph[c]) - (0 in graph[c])

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                queue.append((0, i, t, MOUSE))
                if i > 0:
                    color[i, i, t] = CAT
                    queue.append((i, i, t, CAT))

        # percolate
        while queue:
            # for nodes that are colored :
            i, j, t, c = queue.popleft()
            # for every parent of this node i, j, t :
            for i2, j2, t2 in parents(i, j, t):
                # if this parent is not colored :
                if color[i2, j2, t2] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if t2 == c: # winning move
                        color[i2, j2, t2] = c
                        queue.append((i2, j2, t2, c))
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[i2, j2, t2] -= 1
                        if degree[i2, j2, t2] == 0:
                            color[i2, j2, t2] = 3 - t2
                            queue.append((i2, j2, t2, 3 - t2))

        return color[1, 2, 1]

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        def parent(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 1
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 2
        D, M, C = 0, 1, 2
        color = collections.defaultdict(int)
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m, c, 1] = len(graph[m])
                degree[m, c, 2] = len(graph[c]) - (0 in graph[c])
                
        queue = collections.deque([])
        for i in range(N):
            for t in [1, 2]:
                color[0, i, t] = M
                queue.append((0, i, t, M))
                if i > 0:
                    color[i, i, t] = C
                    queue.append((i, i, t, C))
                    
        while queue:
            i, j, t, w = queue.popleft()
            for i2, j2, t2 in parent(i, j, t):
                if color[i2, j2, t2] is D:
                    if t2 == w:
                        color[i2, j2, t2] = w
                        queue.append((i2, j2, t2, w))
                    else:
                        degree[i2, j2, t2] -= 1
                        if degree[i2, j2, t2] == 0:
                            color[i2, j2, t2] = 3 - t2
                            queue.append((i2, j2, t2, 3-t2))
                            
        return color[1, 2, 1]

class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # * (m c c) = 2, for m' in g[m], if all((m'' c c) = 2 for m'' in g[m']) => (m' c m) = 2
        # return (1 2 m). return once we know its value.

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == 0:
                q.append((m, c, t))
                s[m][c][t] = v

        # approach:

        # set and enqueue initial known states.
        for m in range(n):
            for t in range(2):
                sq(m, 0, t, -1)
        for c in range(n):
            for t in range(2):
                sq(0, c, t, 1)
        for x in range(n):
            for t in range(2):
                sq(x, x, t, 2)

        # while queue:
        while q:
            # pop state.
            m, c, t = state = q.popleft()
            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == 1 and s[m][c][t] == 1:
                for m_ in g[m]:
                    sq(m_, c, 0, 1)

            if t == 0 and s[m][c][t] == 2:
                for c_ in g[c]:
                    sq(m, c_, 1, 2)

            # if t == 0 and s[m][c][t] == 1 and c not in g[m]:
            # sq(m, c, 1, 1)

            if t == 0 and s[m][c][t] == 1:
                for c_ in g[c]:
                    if all(s[m][c__][0] in (-1, 1) for c__ in g[c_]):
                        sq(m, c_, 1, 1)

            if t == 1 and s[m][c][t] == 2:
                for m_ in g[m]:
                    if all(s[m__][c][1] in (-1, 2) for m__ in g[m_]):
                        sq(m_, c, 0, 2)

            # if we know state[1,2,m], return it.
            if s[1][2][0]:
                return s[1][2][0]

        # everything else is a draw.
        return 0


class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # * (m c c) = 2, for m' in g[m], if all((m'' c c) = 2 for m'' in g[m']) => (m' c m) = 2
        # return (1 2 m). return once we know its value.

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == 0:
                q.append((m, c, t))
                s[m][c][t] = v

        # set and enqueue initial known states.
        for m in range(n):
            for t in range(2):
                sq(m, 0, t, -1)
        for c in range(n):
            for t in range(2):
                sq(0, c, t, 1)
        for x in range(n):
            for t in range(2):
                sq(x, x, t, 2)

        while q:
            m, c, t = state = q.popleft()

            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == 1 and s[m][c][t] == 1:
                for m_ in g[m]:
                    sq(m_, c, 0, 1)

            if t == 0 and s[m][c][t] == 2:
                for c_ in g[c]:
                    sq(m, c_, 1, 2)

            if t == 0 and s[m][c][t] == 1:
                for c_ in g[c]:
                    if all(s[m][c__][0] in (-1, 1) for c__ in g[c_]):
                        sq(m, c_, 1, 1)

            if t == 1 and s[m][c][t] == 2:
                for m_ in g[m]:
                    if all(s[m__][c][1] in (-1, 2) for m__ in g[m_]):
                        sq(m_, c, 0, 2)

            # once we know state[1,2,m], return it.
            if s[1][2][0]:
                return s[1][2][0]

        # everything else is a draw.
        return 0


class Solution:
  def catMouseGame(self, graph):
    TIE           = 0
    MOUSE_WIN         = 1
    CAT_WIN         = 2
    MOUSE_TURN        = 'MOUSE'
    CAT_TURN        = 'CAT'
    HOLE_POSITION       = 0
    MPOS_INIT  = 1
    CPOS_INIT  = 2

    win_states = {}
    for m_pos, _ in enumerate(graph):
      for c_pos, _ in enumerate(graph):
        for turn in [MOUSE_TURN, CAT_TURN]:
          key = (m_pos, c_pos, turn)
          if m_pos == HOLE_POSITION:
            # If the mouse reaches the hole, the mouse wins.
            # The cat also isn't allowed to go on the node corresponding
            # to the hole, so mark the cat doing that as also a win.
            win_states[key] = MOUSE_WIN
          elif m_pos == c_pos:
            win_states[key] = CAT_WIN
          else:
            win_states[key] = TIE
    while True:
      num_changed = 0
      turn = MOUSE_TURN
      for m_pos, _ in enumerate(graph):
        for c_pos, _ in enumerate(graph):
          all_cat_win = False
          if win_states[(m_pos, c_pos, turn)] == TIE:
            neighbor_states = [win_states[(node, c_pos, CAT_TURN)] for node in graph[m_pos]]
            if all(win == CAT_WIN for win in neighbor_states):
              win_states[(m_pos, c_pos, turn)] = CAT_WIN
              num_changed += 1
            elif any(win == MOUSE_WIN for win in neighbor_states):
              win_states[(m_pos, c_pos, turn)] = MOUSE_WIN
              num_changed += 1
      turn = CAT_TURN
      for m_pos, _ in enumerate(graph):
        for c_pos, _ in enumerate(graph):
          if win_states[(m_pos, c_pos, turn)] == TIE:
            neighbor_states = [win_states[(m_pos, node, MOUSE_TURN)] for node in graph[c_pos] if node != HOLE_POSITION]
            if all(win == MOUSE_WIN for win in neighbor_states):
              win_states[(m_pos, c_pos, turn)] = MOUSE_WIN
              num_changed += 1
            elif any(win == CAT_WIN for win in neighbor_states):
              win_states[(m_pos, c_pos, turn)] = CAT_WIN
              num_changed += 1
      if num_changed == 0:
        break
    return win_states[(MPOS_INIT, CPOS_INIT, MOUSE_TURN)]


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        CAT_TURN = CAT_WIN = 2
        MOUSE_TURN = MOUSE_WIN = 1
        DRAW = 0
        outcome = defaultdict(int)
        degree = {}
        for cat in range(n):
            cat_neighbour_has_zero = 1 if 0 in graph[cat] else 0
            for mouse in range(n):
                degree[mouse, cat, 1] = len(graph[mouse])
                degree[mouse, cat, 2] = len(graph[cat]) - cat_neighbour_has_zero
                
        queue = deque()
        for cat in range(n):
            for turn in [MOUSE_TURN, CAT_TURN]:
                outcome[0, cat, turn] = MOUSE_WIN
                queue.append((0, cat, turn, MOUSE_WIN))
                if cat > 0:
                    outcome[cat, cat, turn] = CAT_WIN
                    queue.append((cat, cat, turn, CAT_WIN))
                    
        def previous(mouse, cat, turn):
            if turn == MOUSE_TURN:
                for prev_cat in graph[cat]:
                    if prev_cat:
                        yield mouse, prev_cat, 3 - turn
            else:
                for prev_mouse in graph[mouse]:
                    yield prev_mouse, cat, 3 - turn
                    
        while queue:
            mouse, cat, turn, final_outcome = queue.popleft()
            for prev_mouse, prev_cat, prev_turn in previous(mouse, cat, turn):
                if outcome[prev_mouse, prev_cat, prev_turn] == DRAW:
                    if prev_turn == final_outcome:
                        outcome[prev_mouse, prev_cat, prev_turn] = final_outcome
                        queue.append((prev_mouse, prev_cat, prev_turn, final_outcome))
                    else:
                        degree[prev_mouse, prev_cat, prev_turn] -= 1
                        if degree[prev_mouse, prev_cat, prev_turn] == 0:
                            outcome[prev_mouse, prev_cat, prev_turn] = 3 - prev_turn
                            queue.append((prev_mouse, prev_cat, prev_turn, 3 - prev_turn))
        return outcome[1, 2, 1]
        
        
        
        
#         # For n nodes, the possible longest path in the graph is n. If the cat can win, 
#         # its distance to the mouse should decrease, after decease n times if still doesn't 
#         # catch the mouse, and mouse haven't reach node 0 yet, means this is a draw
        
#         # it takes at most n for mouse to get to 0. At 2*n time, it means mouse take a 
#         # detour of at least n steps. It means that there should be at least a loop(size n) 
#         # or multiple loops of (size < n).
        
#         n = len(graph)
#         @lru_cache(None)
#         def move(cat, mouse, t):
#             # should be 2n but 0.8n also passes all tests
#             if t > int(0.8 * n):
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if t % 2 == 0:
#                 best_result = 2
#                 for pos in graph[mouse]:
#                     result = move(cat, pos, t + 1)
#                     if result == 1:
#                         return 1
#                     if result == 0:
#                         best_result = 0
#             else:
#                 best_result = 1
#                 for pos in graph[cat]:
#                     if pos == 0:
#                         continue
#                     result = move(pos, mouse, t + 1)
#                     if result == 2:
#                         return 2
#                     if result == 0:
#                         best_result = 0
#             return best_result
#         return move(2, 1, 0)
        
        
        
        
#         n = len(graph)
#         cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
#         def move(cat, mouse, t):
#             if t == 2 * n:
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if cache[cat][mouse][t] == -1:
#                 mouse_move = (t % 2) == 0
#                 if mouse_move:
#                     best_result = 2
#                     for pos in graph[mouse]:
#                         result = move(cat, pos, t + 1)
#                         if result == 1:
#                             cache[cat][mouse][t] = 1
#                             return 1
#                         if result == 0:
#                             best_result = 0
#                 else:
#                     best_result = 1
#                     for pos in graph[cat]:
#                         if pos == 0:
#                             continue
#                         result = move(pos, mouse, t + 1)
#                         if result == 2:
#                             cache[cat][mouse][t] = 2
#                             return 2
#                         if result == 0:
#                             best_result = 0
#                 cache[cat][mouse][t] = best_result
#             return cache[cat][mouse][t]
#         return move(2, 1, 0)


TIE        = 0
MOUSE_WIN  = 1
CAT_WIN    = 2
MOUSE_TURN = 'MOUSE'
CAT_TURN   = 'CAT'
GOAL       = 0
MPOS_INIT  = 1
CPOS_INIT  = 2

class Solution:
  def catMouseGame(self, graph):
    win_states = {}
    for mpos, _ in enumerate(graph):
      for cpos, _ in enumerate(graph):
        for turn in [MOUSE_TURN, CAT_TURN]:
          key = (mpos, cpos, turn)
          if mpos == GOAL:   win_states[key] = MOUSE_WIN
          elif mpos == cpos: win_states[key] = CAT_WIN
          else:              win_states[key] = TIE
    while True:
      changes = 0
      turn = MOUSE_TURN
      for mpos, adj in enumerate(graph):
        for cpos, _ in enumerate(graph):
          all_cat_win = False
          if win_states[(mpos, cpos, turn)] == TIE:
            adj_wins = [win_states[(node, cpos, CAT_TURN)] for node in adj]
            if all(win == CAT_WIN for win in adj_wins):
              win_states[(mpos, cpos, turn)], changes = CAT_WIN, changes + 1
            elif any(win == MOUSE_WIN for win in adj_wins):
              win_states[(mpos, cpos, turn)], changes = MOUSE_WIN, changes + 1
      turn = CAT_TURN
      for mpos, _ in enumerate(graph):
        for cpos, adj in enumerate(graph):
          if win_states[(mpos, cpos, turn)] == TIE:
            adj_wins = [win_states[(mpos, node, MOUSE_TURN)] for node in adj if node != GOAL]
            if all(win == MOUSE_WIN for win in adj_wins):
              win_states[(mpos, cpos, turn)], changes = MOUSE_WIN, changes + 1
            elif any(win == CAT_WIN for win in adj_wins):
              win_states[(mpos, cpos, turn)], changes = CAT_WIN, changes + 1
      if changes == 0:
        break
    return win_states[(MPOS_INIT, CPOS_INIT, MOUSE_TURN)]


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # For n nodes, the possible longest path in the graph is n. If the cat can win, 
        # its distance to the mouse should decrease, after decease n times if still doesn't 
        # catch the mouse, and mouse haven't reach node 0 yet, means this is a draw
        
        # it takes at most n for mouse to get to 0. At 2*n time, it means mouse take a 
        # detour of at least n steps. It means that there should be at least a loop(size n) 
        # or multiple loops of (size < n).
        
        n = len(graph)
        @lru_cache(None)
        def move(cat, mouse, t):
            if t == 2 * n:
                return 0
            elif mouse == 0:
                return 1
            elif cat == mouse:
                return 2
            if t % 2 == 0:
                best_result = 2
                for pos in graph[mouse]:
                    result = move(cat, pos, t + 1)
                    if result == 1:
                        return 1
                    if result == 0:
                        best_result = 0
            else:
                best_result = 1
                for pos in graph[cat]:
                    if pos == 0:
                        continue
                    result = move(pos, mouse, t + 1)
                    if result == 2:
                        return 2
                    if result == 0:
                        best_result = 0
            return best_result
        return move(2, 1, 0)
        
        
        
#         n = len(graph)
#         cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
#         def move(cat, mouse, t):
#             if t == 2 * n:
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if cache[cat][mouse][t] == -1:
#                 mouse_move = (t % 2) == 0
#                 if mouse_move:
#                     best_result = 2
#                     for pos in graph[mouse]:
#                         result = move(cat, pos, t + 1)
#                         if result == 1:
#                             cache[cat][mouse][t] = 1
#                             return 1
#                         if result == 0:
#                             best_result = 0
#                 else:
#                     best_result = 1
#                     for pos in graph[cat]:
#                         if pos == 0:
#                             continue
#                         result = move(pos, mouse, t + 1)
#                         if result == 2:
#                             cache[cat][mouse][t] = 2
#                             return 2
#                         if result == 0:
#                             best_result = 0
#                 cache[cat][mouse][t] = best_result
#             return cache[cat][mouse][t]
#         return move(2, 1, 0)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (mouse, cat, turn) ?
        def parents(mouse, cat, turn):
            prev_turn = 3 - turn
            if prev_turn == MOUSE: 
                for m2 in graph[mouse]:
                    yield m2, cat, prev_turn
            else:
                for c2 in graph[cat]:
                    if c2:
                        yield mouse, c2, prev_turn

        DRAW, MOUSE, CAT = 0, 1, 2
        colors = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for mouse in range(N):
            for cat in range(N):
                degree[mouse, cat, MOUSE] = len(graph[mouse])
                degree[mouse, cat, CAT] = len(graph[cat]) - (0 in graph[cat])  # cat can not be at hole 0

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for cat in range(N):
            for turn in [MOUSE, CAT]:
                # color MOUSE for all node with mouse=0
                mouse = 0
                colors[mouse, cat, turn] = MOUSE
                queue.append((mouse, cat, turn, MOUSE))
                # color CAT for all node with mouse = cat !=0, cat can not be at hole 0
                if cat > 0:
                    mouse = cat
                    colors[mouse, cat, turn] = CAT
                    queue.append((mouse, cat, turn, CAT))

        # percolate
        while queue:
            mouse, cat, turn, color = queue.popleft()
            for prev_mouse, prev_cat, prev_turn in parents(mouse, cat, turn):
                # if this parent is not colored :
                if colors[prev_mouse, prev_cat, prev_turn] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if prev_turn == color: # winning move
                        colors[prev_mouse, prev_cat, prev_turn] = color
                        queue.append((prev_mouse, prev_cat, prev_turn, color))
                        if prev_mouse == 1 and prev_cat == 2 and prev_turn == MOUSE: 
                            return color
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[prev_mouse, prev_cat, prev_turn] -= 1
                        # if prev_turn != color, and all of its children are of this color
                        # then prev color should be this color too
                        if degree[prev_mouse, prev_cat, prev_turn] == 0:
                            colors[prev_mouse, prev_cat, prev_turn] = color
                            queue.append((prev_mouse, prev_cat, prev_turn, color))
                            if prev_mouse == 1 and prev_cat == 2 and prev_turn == MOUSE: 
                                return color

        return colors[1, 2, 1] # mouse at 1, cat at 2, MOUSE turn


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        MOUSE = 1
        CAT = 2
        DRAW = 0
        states = collections.defaultdict(lambda: DRAW)
        
        
        
        n = len(graph) 
        for i in range(1, n):
            states[i, i, MOUSE] = CAT
            states[i, i, CAT] = CAT
            states[0, i, MOUSE] = MOUSE
            states[0, i, CAT] = MOUSE
            
        draws = dict()
        for mouse in range(n):
            for cat in range(1, n):
                draws[mouse, cat, CAT] = len(graph[cat]) - (0 in graph[cat])
                draws[mouse, cat, MOUSE] = len(graph[mouse])
                    
                    
                        
                        
        def neighbor(mouse, cat, turn):
            prev_turn = CAT if turn == MOUSE else MOUSE
            if prev_turn == MOUSE:
                for prev_mouse in graph[mouse]:
                    yield prev_mouse, cat, prev_turn
            else:
                for prev_cat in graph[cat]:
                    if prev_cat != 0:
                        yield mouse, prev_cat, prev_turn
        
        queue = collections.deque()
        for state in states.keys():
            queue.append(state)
        
        while len(queue) > 0:
            state = queue.popleft()
            mouse, cat, turn = state
            win = states[state]
            
            for prev_state in neighbor(*state):
                prev_mouse, prev_cat, prev_turn = prev_state
                if states[prev_state] != DRAW:
                    continue
                elif prev_turn == win:
                    states[prev_state] = win
                    queue.append(prev_state)
                else:
                    draws[prev_state] -= 1
                    if draws[prev_state] == 0:
                        states[prev_state] = turn
                        queue.append(prev_state)
                
        return states[1, 2, MOUSE]

class Solution:
    # minimax
    # https://www.youtube.com/watch?v=WJ7uqznd_4s
    def catMouseGame(self, graph: List[List[int]]) -> int:
        memo = {}

        def mouse_play(key, cat, mouse, turn):
            if any(v == 0 for v in graph[mouse]):
                memo[key] = 1
                return 1
            res = 2
            for nxt in graph[mouse]:
                # mouse reach 0, mouse wins
                # mouse would not run int place cat holds now
                if nxt == cat:
                    continue
                tmp = move(cat, nxt, False)
                # if mouse win, directly break, mouse would always take the optimal solution
                if tmp == 1:
                    res = 1
                    break
                if tmp == 0:
                    res = 0
            memo[key] = res

            return res

        def cat_play(key, cat, mouse, turn):
            if any(v == mouse for v in graph[cat]):
                memo[key] = 2
                return 2
            res = 1
            for nxt in graph[cat]:
                # if nxt == mouse:
                #     memo[key] = 2
                #     return 2
                # cat can not enter hole
                if nxt == 0:
                    continue
                tmp = move(nxt, mouse, True)
                if tmp == 2:
                    res = 2
                    break
                if tmp == 0:
                    res = 0
            memo[key] = res

            return res

        def move(cat, mouse, turn):
            key = (cat, mouse, turn)
            if key in memo:
                return memo[key]

            memo[key] = 0

            if turn:
                return mouse_play(key, cat, mouse, turn)
            else:
                return cat_play(key, cat, mouse, turn)

        return move(2, 1, True)

    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        DRAW, MOUSE, CAT = 0, 1, 2

        def parents(m, c, t):
            if t == MOUSE:
                for c2 in graph[c]:
                    if c2:  # cat can not enter 0
                        yield m, c2, 3 - t
            if t == CAT:
                for m2 in graph[m]:
                    yield m2, c, 3 - t

        color, degree = collections.defaultdict(int), {}

        # (mouse, cat, turn), got the parents/children of this node, [[2,3],...], since the graph is un-directed
        # you can say 2,3 -> 0 (parents) or 0 -> (2,3) children, here we regard it as parents
        for m in range(N):
            for c in range(N):
                degree[m, c, MOUSE] = len(graph[m])
                degree[m, c, CAT] = len(graph[c]) - (0 in graph[c])

        que = collections.deque()
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                que.append((0, i, t))
                if i > 0:
                    color[i, i, t] = CAT
                    que.append((i, i, t))

        while que:
            m, c, t = que.pop()
            col = color[m, c, t]
            # for (m,c,t)'s parents, if
            for m2, c2, t2 in parents(m, c, t):
                if color[m2, c2, t2] is DRAW:
                    if t2 == col:  # mouse 's turn and it goes to MOUSE, or cat's turn, go to CAT
                        color[m2, c2, t2] = col
                        que.append((m2, c2, t2))
                    else:
                        # (m2,c2,t2) is (m,c,t)'s parent, if cat went to MOUSE, or mouse went to CAT,
                        # this is a lose situation, degree -=1, which means we have a losing for its
                        # one children, if all chidren are losing for this parent, ie, degree == 0
                        # then we add it to queue
                        degree[m2, c2, t2] -= 1
                        if not degree[m2, c2, t2]:
                            color[m2, c2, t2] = 3 - t2
                            que.append((m2, c2, t2))

        return color[1, 2, 1]




class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # * (m c c) = 2, for m' in g[m], if all((m'' c c) = 2 for m'' in g[m']) => (m' c m) = 2
        # return (1 2 m). return once we know its value.

        MTURN, CTURN = 0, 1
        ILLEGAL, UNKNOWN, MWIN, CWIN = -1, 0, 1, 2

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == UNKNOWN:
                q.append((m, c, t))
                s[m][c][t] = v

        # set and enqueue initial known states.
        for t in (MTURN, CTURN):
            for m in range(n):
                sq(m, 0, t, ILLEGAL)
            for c in range(n):
                sq(0, c, t, MWIN)
            for x in range(n):
                sq(x, x, t, CWIN)

        while q:
            m, c, t = state = q.popleft()

            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == CTURN and s[m][c][t] == MWIN:
                for m_ in g[m]:
                    sq(m_, c, MTURN, MWIN)

            if t == MTURN and s[m][c][t] == CWIN:
                for c_ in g[c]:
                    sq(m, c_, CTURN, CWIN)

            if t == MTURN and s[m][c][t] == MWIN:
                for c_ in g[c]:
                    if all(s[m][c__][MTURN] in (ILLEGAL, MWIN) for c__ in g[c_]):
                        sq(m, c_, CTURN, MWIN)

            if t == CTURN and s[m][c][t] == CWIN:
                for m_ in g[m]:
                    if all(s[m__][c][CTURN] in (ILLEGAL, CWIN) for m__ in g[m_]):
                        sq(m_, c, MTURN, CWIN)

            # once we know state[1,2,m], return it.
            if s[1][2][MTURN]:
                return s[1][2][MTURN]

        # everything else is a draw.
        return 0


class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # * (m c c) = 2, for m' in g[m], if all((m'' c c) = 2 for m'' in g[m']) => (m' c m) = 2
        # return (1 2 m). return once we know its value.

        MTURN, CTURN = 0, 1
        ILLEGAL, UNKNOWN, MWIN, CWIN = -1, 0, 1, 2

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == UNKNOWN:
                q.append((m, c, t))
                s[m][c][t] = v

        # set and enqueue initial known states.
        for t in (MTURN, CTURN):
            for x in range(n):
                sq(x, 0, t, ILLEGAL)
                sq(0, x, t, MWIN)
                sq(x, x, t, CWIN)

        while q:
            m, c, t = state = q.popleft()

            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == CTURN and s[m][c][t] == MWIN:
                for m_ in g[m]:
                    sq(m_, c, MTURN, MWIN)

            if t == MTURN and s[m][c][t] == CWIN:
                for c_ in g[c]:
                    sq(m, c_, CTURN, CWIN)

            if t == MTURN and s[m][c][t] == MWIN:
                for c_ in g[c]:
                    if all(s[m][c__][MTURN] in (ILLEGAL, MWIN) for c__ in g[c_]):
                        sq(m, c_, CTURN, MWIN)

            if t == CTURN and s[m][c][t] == CWIN:
                for m_ in g[m]:
                    if all(s[m__][c][CTURN] in (ILLEGAL, CWIN) for m__ in g[m_]):
                        sq(m_, c, MTURN, CWIN)

            # once we know state[1,2,m], return it.
            if s[1][2][MTURN]:
                return s[1][2][MTURN]

        # everything else is a draw.
        return 0


class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # * (m c c) = 2, for m' in g[m], if all((m'' c c) = 2 for m'' in g[m']) => (m' c m) = 2
        # return (1 2 m). return once we know its value.

        MTURN, CTURN = 0, 1
        ILLEGAL, UNKNOWN, MWIN, CWIN = -1, 0, 1, 2

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == UNKNOWN:
                q.append((m, c, t))
                s[m][c][t] = v

        # set and enqueue initial known states.
        for t in (MTURN, CTURN):
            for x in range(n):
                sq(x, 0, t, ILLEGAL)
                sq(0, x, t, MWIN)
                sq(x, x, t, CWIN)

        while q:
            m, c, t = q.popleft()

            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == CTURN and s[m][c][t] == MWIN:
                for m_ in g[m]:
                    sq(m_, c, MTURN, MWIN)

            if t == MTURN and s[m][c][t] == CWIN:
                for c_ in g[c]:
                    sq(m, c_, CTURN, CWIN)

            if t == MTURN and s[m][c][t] == MWIN:
                for c_ in g[c]:
                    if all(s[m][c__][MTURN] in (ILLEGAL, MWIN) for c__ in g[c_]):
                        sq(m, c_, CTURN, MWIN)

            if t == CTURN and s[m][c][t] == CWIN:
                for m_ in g[m]:
                    if all(s[m__][c][CTURN] in (ILLEGAL, CWIN) for m__ in g[m_]):
                        sq(m_, c, MTURN, CWIN)

            # once we know state[1,2,m], return it.
            if s[1][2][MTURN]:
                return s[1][2][MTURN]

        # everything else is a draw.
        return 0


from functools import lru_cache


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        MOUSE, CAT, DRAW = 1, 2, 0
        
        @lru_cache(None)
        def winner(mouse, cat, turn):
            if turn >= len(graph)*2:
                return DRAW
            if turn%2 == 0:
                if 0 in graph[mouse]:
                    return MOUSE
                answer = CAT
                for i in graph[mouse]:
                    if i == cat:
                        continue
                    result = winner(i, cat, turn+1)
                    if result == MOUSE:
                        return MOUSE
                    if result == DRAW:
                        answer = DRAW
                return answer
            else:
                if mouse in graph[cat]:
                    return CAT
                answer = MOUSE
                for i in graph[cat]:
                    if i == 0:
                        continue
                    result = winner(mouse, i, turn+1)
                    if result == CAT:
                        return CAT
                    if result == DRAW:
                        answer = DRAW
                return answer
        
        return winner(1, 2, 0)

from collections import deque, defaultdict


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        DRAW, MOUSE, CAT = 0, 1, 2
        
        def parents(m, c, t):
            if t == MOUSE:
                return [(m, x, CAT) for x in graph[c] if x != 0]
            return [(x, c, MOUSE) for x in graph[m]]
                    
        color = defaultdict(int)
        for t in MOUSE, CAT:
            for x in range(n):
                color[0, x, t] = MOUSE
                if x != 0:
                    color[x, x, t] = CAT
                    
        degree = {}
        for m in range(n):
            for c in range(n):
                degree[m, c, MOUSE] = len(parents(m, c, CAT))
                degree[m, c, CAT] = len(parents(m, c, MOUSE))

        q = deque()
        for k, v in color.items():
            q.append((*k, v))
        
        while q:
            m, c, t, winner = q.popleft()
            for m2, c2, t2 in parents(m, c, t):
                if color[m2, c2, t2] != DRAW:
                    continue
                
                if t2 == winner:
                    color[m2, c2, t2] = winner
                    q.append((m2, c2, t2, winner))
                else:
                    degree[m2, c2, t2] -= 1
                    if degree[m2, c2, t2] == 0:
                        color[m2, c2, t2] = t
                        q.append((m2, c2, t2, t))
        
        return color[1, 2, 1]

from collections import deque, defaultdict


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        DRAW, MOUSE, CAT = 0, 1, 2
        
        def parents(m, c, t):
            if t == MOUSE:
                return [(m, x, CAT) for x in graph[c] if x != 0]
            return [(x, c, MOUSE) for x in graph[m]]
                    
        color = defaultdict(int)
        for t in MOUSE, CAT:
            for x in range(n):
                color[0, x, t] = MOUSE
                if x != 0:
                    color[x, x, t] = CAT
                    
        degree = {}
        for m in range(n):
            for c in range(n):
                degree[m, c, MOUSE] = len(parents(m, c, CAT))
                degree[m, c, CAT] = len(parents(m, c, MOUSE))

        q = deque()
        for k, v in color.items():
            q.append((*k, v))
        
        while q:
            m, c, t, winner = q.popleft()
            for m2, c2, t2 in parents(m, c, t):
                if color[m2, c2, t2] != DRAW:
                    continue
                
                if t2 == winner:
                    color[m2, c2, t2] = winner
                    q.append((m2, c2, t2, winner))
                else:
                    degree[m2, c2, t2] -= 1
                    if degree[m2, c2, t2] == 0:
                        color[m2, c2, t2] = winner
                        q.append((m2, c2, t2, winner))
        
        return color[1, 2, 1]

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: 
                return 0
            if x == y:
                return 2
            if x == 0:
                return 1
            
            if (t%2==0):
                flag = True
                for i in range(len(graph[x])):
                    nxt = search(t+1, graph[x][i], y)
                    if nxt == 1:
                        return 1
                    elif nxt!=2:
                        flag = False
                if flag:
                    return 2
                return 0
            else:
                flag = True
                for i in range(len(graph[y])):
                    if graph[y][i]!=0:
                        nxt = search(t + 1, x, graph[y][i])
                        if nxt ==2:
                            return 2
                        elif nxt != 1:
                            flag=False
                if flag:
                    return 1
                else:
                    return 0
        n = len(graph)

        return search(0, 1, 2)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        CAT_TURN = CAT_WIN = 2
        MOUSE_TURN = MOUSE_WIN = 1
        DRAW = 0
        outcome = defaultdict(int)
        degree = {}
        for cat in range(n):
            cat_neighbour_has_zero = 1 if 0 in graph[cat] else 0
            for mouse in range(n):
                degree[mouse, cat, 1] = len(graph[mouse])
                degree[mouse, cat, 2] = len(graph[cat]) - cat_neighbour_has_zero
                
        queue = deque()
        for cat in range(n):
            for turn in [MOUSE_TURN, CAT_TURN]:
                outcome[0, cat, turn] = MOUSE_WIN
                queue.append((0, cat, turn, MOUSE_WIN))
                if cat > 0:
                    outcome[cat, cat, turn] = CAT_WIN
                    queue.append((cat, cat, turn, CAT_WIN))
                    
        def previous(mouse, cat, turn):
            if turn == MOUSE_TURN:
                for prev_cat in graph[cat]:
                    if prev_cat:
                        yield mouse, prev_cat, 3 - turn
            else:
                for prev_mouse in graph[mouse]:
                    yield prev_mouse, cat, 3 - turn
         
        target = (1, 2, 1)
        while queue:
            mouse, cat, turn, final_outcome = queue.popleft()
            for prev_mouse, prev_cat, prev_turn in previous(mouse, cat, turn):
                if outcome[prev_mouse, prev_cat, prev_turn] == DRAW:
                    if prev_turn == final_outcome:
                        outcome[prev_mouse, prev_cat, prev_turn] = final_outcome
                        if (prev_mouse, prev_cat, prev_turn) == target:
                            return final_outcome
                        queue.append((prev_mouse, prev_cat, prev_turn, final_outcome))
                    else:
                        degree[prev_mouse, prev_cat, prev_turn] -= 1
                        if degree[prev_mouse, prev_cat, prev_turn] == 0:
                            if (prev_mouse, prev_cat, prev_turn) == target:
                                return 3 - prev_turn
                            outcome[prev_mouse, prev_cat, prev_turn] = 3 - prev_turn
                            queue.append((prev_mouse, prev_cat, prev_turn, 3 - prev_turn))
        return outcome[1, 2, 1]
        
        
        
        
#         # For n nodes, the possible longest path in the graph is n. If the cat can win, 
#         # its distance to the mouse should decrease, after decease n times if still doesn't 
#         # catch the mouse, and mouse haven't reach node 0 yet, means this is a draw
        
#         # it takes at most n for mouse to get to 0. At 2*n time, it means mouse take a 
#         # detour of at least n steps. It means that there should be at least a loop(size n) 
#         # or multiple loops of (size < n).
        
#         n = len(graph)
#         @lru_cache(None)
#         def move(cat, mouse, t):
#             # should be 2n but 0.8n also passes all tests
#             if t > int(0.8 * n):
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if t % 2 == 0:
#                 best_result = 2
#                 for pos in graph[mouse]:
#                     result = move(cat, pos, t + 1)
#                     if result == 1:
#                         return 1
#                     if result == 0:
#                         best_result = 0
#             else:
#                 best_result = 1
#                 for pos in graph[cat]:
#                     if pos == 0:
#                         continue
#                     result = move(pos, mouse, t + 1)
#                     if result == 2:
#                         return 2
#                     if result == 0:
#                         best_result = 0
#             return best_result
#         return move(2, 1, 0)
        
        
        
        
#         n = len(graph)
#         cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
#         def move(cat, mouse, t):
#             if t == 2 * n:
#                 return 0
#             elif mouse == 0:
#                 return 1
#             elif cat == mouse:
#                 return 2
#             if cache[cat][mouse][t] == -1:
#                 mouse_move = (t % 2) == 0
#                 if mouse_move:
#                     best_result = 2
#                     for pos in graph[mouse]:
#                         result = move(cat, pos, t + 1)
#                         if result == 1:
#                             cache[cat][mouse][t] = 1
#                             return 1
#                         if result == 0:
#                             best_result = 0
#                 else:
#                     best_result = 1
#                     for pos in graph[cat]:
#                         if pos == 0:
#                             continue
#                         result = move(pos, mouse, t + 1)
#                         if result == 2:
#                             cache[cat][mouse][t] = 2
#                             return 2
#                         if result == 0:
#                             best_result = 0
#                 cache[cat][mouse][t] = best_result
#             return cache[cat][mouse][t]
#         return move(2, 1, 0)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        
        def parents(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 3-t
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 3-t
        
        DRAW, MOUSE, CAT=0,1,2
        color = collections.defaultdict(int)
        
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m,c,1] = len(graph[m])
                degree[m,c,2] = len(graph[c]) - (0 in graph[c])
        
        queue = collections.deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0,i,t] = MOUSE
                queue.append((0,i,t,MOUSE))
                if i > 0:
                    color[i,i,t] = CAT
                    queue.append((i,i,t,CAT))
        
        while queue:
            i, j, t, c = queue.popleft()
            for i2, j2, t2 in parents(i, j, t):
                # if this parent node is not colored
                if color[i2,j2,t2] is DRAW:
                    if t2 == c:#winning move
                        color[i2,j2,t2] = c
                        queue.append((i2,j2,t2,c))
                    else:
                        degree[i2,j2,t2] -= 1
                        if degree[i2,j2,t2] == 0:
                            color[i2,j2,t2] = 3-t2
                            queue.append((i2,j2,t2,3-t2))
        return color[1,2,1]
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        # dp[t][i][j] := game outcome when at time t, mouse at i, cat at j
        ## 0: draw, 1: mouse wins, 2: cat wins
        dp = [[[-1]*N for _ in range(N)] for m in range(2*N)]
        
        for m in range(2*N):
            for i in range(N):
                dp[m][i][i] = 2 # win by cat
                dp[m][0][i] = 1 # win by mouse
        # dp = 0 when m==2N
        
        def _search(t, x, y):
            # time, mouse pos, cat pos
            if t==2*N: return 0
            if dp[t][x][y]!=-1: return dp[t][x][y]
            
            if t%2==0: # mouse's turn
                winByCat = True
                for i in graph[x]:
                    nxt = _search(t+1, i, y)
                    if nxt==1:
                        dp[t][x][y] = 1
                        return 1
                    if nxt!=2:
                        winByCat = False
                if winByCat:
                    dp[t][x][y] = 2
                    return 2
                else:
                    dp[t][x][y] = 0
                    return 0
            else: # cat's turn
                winByMouse = True
                for i in graph[y]:
                    if i!=0: # cat cannot be at the hole -- 0
                        nxt = _search(t+1, x, i)
                        if nxt==2:
                            dp[t][x][y] = 2
                            return 2
                        if nxt!=1:
                            winByMouse = False
                if winByMouse:
                    dp[t][x][y] = 1
                    return 1
                else:
                    dp[t][x][y] = 0
                    return 0
        
        
        return _search(0, 1, 2)

from functools import lru_cache
from collections import defaultdict
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        adj = defaultdict(list)
        for i in range(len(graph)):
            for j in graph[i]:
                adj[i].append(j)
                adj[j].append(i)
        
        @lru_cache(None)
        def search(m: int, c: int, turn: int, time: int) -> int:
            # 1: mouse wins, 2: cat wins, 0: draw
            if m == 0:
                return 1
            elif m == c:
                return 2
            elif time >= 50:
                return 0
            if turn == 0: # mouse moves
                can_draw = False
                for y in adj[m]:
                    res = search(y, c, 1 - turn, time + 1)
                    if res == 1:
                        return 1
                    elif res == 0:
                        can_draw = True
                return 0 if can_draw else 2
            else:
                can_draw = False
                for y in adj[c]:
                    if y == 0:
                        continue
                    res = search(m, y, 1 - turn, time + 1)
                    if res == 2:
                        return 2
                    elif res == 0:
                        can_draw = True
                return 0 if can_draw else 1
        
        return search(1, 2, 0, 0)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        encode = lambda p, c, m: (c << 7) | (m << 1) | p
        # encode = lambda p, c, m: (p, c, m)
        decode = lambda c: (c & 0x1, c >> 7, (c >> 1) & 0x3f)
        n = len(graph)
        g = collections.defaultdict(list)
        outcomes = {}
        degrees = collections.Counter()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    status = encode(p, c, m)
                    if p == 0:
                        if c == m:
                            outcomes[status] = 1
                        elif m == 0:
                            outcomes[status] = -1
                    else:
                        if m == 0:
                            outcomes[status] = 1
                        elif c == m:
                            outcomes[status] = -1
                    if outcomes.get(status, 0):
                        continue
                    if p == 0:
                        for i in graph[c]:
                            if i == 0: continue
                            st = encode((p + 1) % 2, i, m)
                            g[st].append(status)
                            degrees[status] += 1
                    else:
                        for i in graph[m]:
                            st = encode((p + 1) % 2, c, i)
                            g[st].append(status)
                            degrees[status] += 1
        # for st, nei in g.items():
        #     print(st, nei)
        # print(outcomes)
        def dfs(status):
            visited.add(status)
            if status == initial:
                return True
            for st in g[status]:
                if st not in visited:
                    if outcomes[status] == -1:
                        outcomes[st] = 1
                    else:
                        degrees[st] -= 1
                        if degrees[st] == 0:
                            outcomes[st] = -1
                        else:
                            continue
                    if dfs(st):
                        return True
            return False
        visited = set()
        initial = encode(1, 2, 1)
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    st = encode(p, c, m)
                    if outcomes.get(st, 0) and st not in visited:
                        if dfs(st):
                            o = outcomes.get(encode(1, 2, 1), 0)
                            if o == -1:
                                o = 2
                            return o
        return 0
        


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        dp = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
        return self.search(graph, dp, 1, 2, 0)
        
    def search(self, graph, dp, x, y, z):
        if z == 2 * len(graph): return 0
        if dp[x][y][z] == -1:     
            if x == 0: res = 1
            elif x == y: res = 2
            elif z % 2 == 0:
                draw, res = False, None
                for nx in graph[x]:
                    ans = self.search(graph, dp, nx, y, z + 1)
                    if ans == 1:
                        res = 1
                        break
                    elif ans == 0:
                        draw = True
                res = res if res else (0 if draw else 2)
            else:
                draw, res = False, None
                for ny in graph[y]:
                    if ny == 0: continue
                    ans = self.search(graph, dp, x, ny, z + 1)
                    if ans == 2:
                        res = 2
                        break
                    elif ans == 0:
                        draw = True
                res = res if res else (0 if draw else 1)
            dp[x][y][z] = res
        return dp[x][y][z]

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        cache = [[[-1] * (2 * n) for _ in range(n)] for _ in range(n)]
        def move(cat, mouse, t):
            if t == 2 * n:
                return 0
            elif mouse == 0:
                return 1
            elif cat == mouse:
                return 2
            if cache[cat][mouse][t] == -1:
                mouse_move = (t % 2) == 0
                if mouse_move:
                    best_result = 2
                    for pos in graph[mouse]:
                        result = move(cat, pos, t + 1)
                        if result == 1:
                            cache[cat][mouse][t] = 1
                            return 1
                        if result == 0:
                            best_result = 0
                else:
                    best_result = 1
                    for pos in graph[cat]:
                        if pos == 0:
                            continue
                        result = move(pos, mouse, t + 1)
                        if result == 2:
                            cache[cat][mouse][t] = 2
                            return 2
                        if result == 0:
                            best_result = 0
                cache[cat][mouse][t] = best_result
            return cache[cat][mouse][t]
        return move(2, 1, 0)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def dp(mp, cp, turn):
            if turn>=N: return 0
            if mp==0: return 1
            if mp==cp: return 2
            
            if (mp, cp, turn) in memo: return memo[(mp, cp, turn)]
            
            res = 0
            if turn%2==0:
                if any(dp(nxt, cp, turn+1)==1 for nxt in graph[mp]):
                    res = 1
                elif all(dp(nxt, cp, turn+1)==2 for nxt in graph[mp]):
                    res = 2
            else:
                if any(dp(mp, nxt, turn+1)==2 for nxt in graph[cp] if nxt!=0):
                    res = 2
                elif all(dp(mp, nxt, turn+1)==1 for nxt in graph[cp] if nxt!=0):
                    res = 1
                        
            memo[(mp, cp, turn)] = res
            return res
                    
        N = len(graph)
        memo = {}
        return dp(1, 2, 0)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: 
                return 0
            if x == y:
                return 2
            if x == 0:
                return 1
            
            if (t%2==0):
                flag = True
                for i in range(len(graph[x])):
                    nxt = search(t+1, graph[x][i], y)
                    if nxt == 1:
                        return 1
                    elif nxt!=2:
                        flag = False
                if flag:
                    return 2
                return 0
            else:
                flag = True
                for i in range(len(graph[y])):
                    if graph[y][i]!=0:
                        nxt = search(t + 1, x, graph[y][i])
                        if nxt ==2:
                            return 2
                        elif nxt != 1:
                            flag=False
                if flag:
                    return 1
                else:
                    return 0
        n = len(graph)
        dp = [ [ [-1 for k in range(n)] for j in range(n)] for i in range(2*n)]
        return search(0, 1, 2)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        lim = 2 * N
        
        @lru_cache(maxsize=None)
        def _visit(state: Tuple[int, int, int], t):
            if t >= lim:
                return 0

            x, y, p = state
            if x == 0:
                return 1
            elif x == y :
                return 2
            
            if p == 1:
                it = (_visit((n, y, 2), t+1) for n in graph[x])
            else:
                it = (_visit((x, n, 1), t+1) for n in graph[y] if n != 0)
            
            update = 1 if p == 2 else 2
            
            for v in it:
                if v == p:
                    return p
                elif v == 0:
                    update = 0
            
            return update

        r = _visit((1, 2, 1), 0)
        return r

class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        
        # status: current_mouse_position, current_cat_position, move_next(0 : mouse, 1 : cat)
        
        for i in range(len(g)):
            g[i] = set(g[i])
        
        out_degree = {}
        for mouse in range(len(g)):
            for cat in range(1, len(g)):
                out_degree[(mouse, cat, 0)] = len(g[mouse])
                out_degree[(mouse, cat, 1)] = len(g[cat]) - (0 in g[cat])
        
        
        visit = set()
        status_result = deque()
        for cat in range(1, len(g)):
            status_result.append([0, cat, 1, 1])
            status_result.append([0, cat, 0, 1])
            visit.add((0, cat, 1))
            visit.add((0, cat, 0))
            
        for mouse in range(1, len(g)):
            status_result.append([mouse, mouse, 0, 2])
            status_result.append([mouse, mouse, 1, 2])
            visit.add((mouse, mouse, 0))
            visit.add((mouse, mouse, 1))
        
        idx = 0
        while len(status_result):
            idx += 1
            # print(status_result)
            mouse, cat, move_next, result = status_result.popleft()
            if mouse == 1 and cat == 2 and move_next == 0:
                return result
            move_prev = 1 - move_next
            if move_prev == 0:
                for p in g[mouse]:
                    if result == 1:
                        if (p, cat, 0) not in visit:
                            status_result.append([p, cat, 0, 1])
                            visit.add((p, cat, 0))
                    else:
                        out_degree[(p, cat, 0)] -= 1
                        if out_degree[(p, cat, 0)] == 0 and (p, cat, 0) not in visit:
                            status_result.append([p, cat, 0, 2])
                            visit.add((p, cat, 0))
            elif move_prev == 1:
                for p in g[cat]:
                    if p != 0:
                        if result == 2:
                            if (mouse, p, 1) not in visit:
                                status_result.append([mouse, p, 1, 2])
                                visit.add((mouse, p, 1))
                        else:
                            out_degree[(mouse, p, 1)] -= 1
                            if out_degree[(mouse, p, 1)] == 0 and (mouse, p, 1) not in visit:
                                status_result.append([mouse, p, 1, 1])
                                visit.add((mouse, p, 1))
        return 0
                    
                    


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        self.dp = [[[-1]*n for _ in range(n)] for _ in range(2*n)]
        def helper(t, x, y):
            if t==2*n: return 0
            if x==y:
                self.dp[t][x][y]=2
                return 2
            if x==0:
                self.dp[t][x][y]=1
                return 1
            if self.dp[t][x][y]!=-1:
                return self.dp[t][x][y]
            mouseTurn = t%2==0
            if mouseTurn:
                catWins=True
                for nei in graph[x]:
                    tmp = helper(t+1, nei, y)
                    if tmp==1:
                        self.dp[t][x][y]=1
                        return 1
                    if tmp!=2:
                        catWins=False
                if catWins:
                    self.dp[t][x][y]=2
                    return 2
                else:
                    self.dp[t][x][y]=0
                    return 0
            else:
                mouseWins=True
                for nei in graph[y]:
                    if nei==0: continue
                    tmp = helper(t+1, x, nei)
                    if tmp==2:
                        self.dp[t][x][y]=2
                        return 2
                    if tmp!=1:
                        mouseWins=False
                if mouseWins:
                    self.dp[t][x][y]=1
                    return 1
                else:
                    self.dp[t][x][y]=0
                    return 0
            return self.dp[t][x][y]
        return helper(0, 1, 2)

class Solution:
    def catMouseGame(self, graph):
        TIE                     = 0
        MOUSE_WIN               = 1
        CAT_WIN                 = 2
        MOUSE_TURN              = 'MOUSE'
        CAT_TURN                = 'CAT'
        HOLE_POSITION           = 0
        INITIAL_MOUSE_POSITION  = 1
        INITIAL_CAT_POSITION    = 2

        win_states = {}
        for m_pos, _ in enumerate(graph):
            for c_pos, _ in enumerate(graph):
                for turn in [MOUSE_TURN, CAT_TURN]:
                    key = (m_pos, c_pos, turn)
                    if m_pos == 0 or c_pos == 0:
                        # If the mouse reaches the hole, the mouse wins.
                        # The cat also isn't allowed to go on the node corresponding
                        # to the hole, so mark the cat doing that as also a win.
                        win_states[key] = MOUSE_WIN
                    elif m_pos == c_pos:
                        win_states[key] = CAT_WIN
                    else:
                        win_states[key] = TIE
        for node_id in graph:
            turn = MOUSE_TURN
            for m_pos, _ in enumerate(graph):
                for c_pos, _ in enumerate(graph):
                    all_cat_win = False
                    if win_states[(m_pos, c_pos, turn)] == TIE:
                        neighbor_states = [win_states[(node, c_pos, CAT_TURN)] for node in graph[m_pos]]
                        if all(win == CAT_WIN for win in neighbor_states):
                            win_states[(m_pos, c_pos, turn)] = CAT_WIN
                        elif any(win == MOUSE_WIN for win in neighbor_states):
                            win_states[(m_pos, c_pos, turn)] = MOUSE_WIN
            turn = CAT_TURN
            for m_pos, _ in enumerate(graph):
                for c_pos, _ in enumerate(graph):
                    if win_states[(m_pos, c_pos, turn)] == TIE:
                        neighbor_states = [win_states[(m_pos, node, MOUSE_TURN)] for node in graph[c_pos]]
                        if all(win == MOUSE_WIN for win in neighbor_states):
                            win_states[(m_pos, c_pos, turn)] = MOUSE_WIN
                        elif any(win == CAT_WIN for win in neighbor_states):
                            win_states[(m_pos, c_pos, turn)] = CAT_WIN

        return win_states[(1, 2, MOUSE_TURN)]


class Solution:
    # O(n^4) time, O(n^3) space
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        edges = defaultdict(list)
        for i, nbrs in enumerate(graph):
            for nbr in nbrs:
                edges[i].append(nbr)
                edges[nbr].append(i)
        
        # cache = {}
        @lru_cache(None)
        def can_win(cat_pos, mouse_pos, remaining_moves, is_cats_turn):
            # state = cat_pos, mouse_pos, is_cats_turn, remaining_moves
            # if state in cache:
            #     return cache[state]
            if mouse_pos == 0:  # mouse wins
                if is_cats_turn:
                    # cache[state] = -1
                    return -1
                # cache[state] = 1
                return 1
            if cat_pos == mouse_pos:  # cat wins
                if is_cats_turn:
                    # cache[state] = 1
                    return 1
                # cache[state] = -1
                return -1
            if remaining_moves == 0:  # draw
                # cache[state] = 0
                return 0
            
            opponents_worst_case = 1
            if is_cats_turn:
                for nbr in edges[cat_pos]:
                    if nbr == 0:
                        continue
                    opponents_worst_case = min(
                        opponents_worst_case, can_win(nbr, mouse_pos, remaining_moves - 1, not is_cats_turn)
                    )
            else:
                for nbr in edges[mouse_pos]:
                    opponents_worst_case = min(
                        opponents_worst_case, can_win(cat_pos, nbr, remaining_moves - 1, not is_cats_turn)
                    )
            
            # cache[state] = -opponents_worst_case
            return -opponents_worst_case
        
        mouse_outcome = can_win(2, 1, 2 * n, False)
        if mouse_outcome == 1:
            return 1
        if mouse_outcome == -1:
            return 2
        return 0
    
#     def catMouseGame(self, graph: List[List[int]]) -> int:
#         n = len(graph)
#         edges = defaultdict(list)
#         for i, nbrs in enumerate(graph):
#             for nbr in nbrs:
#                 edges[i].append(nbr)
#                 edges[nbr].append(i)
        
#         q = [(1, 2)]
#         seen = set()
#         seen.add((1, 2))
#         step = 0
#         is_mouses_turn = True
#         while q:
#             if step > 2 * n:
#                 break
#             # last round is cat's turn
#             if is_mouses_turn and any(cat_pos == mouse_pos for mouse_pos, cat_pos in q):
#                 return 2
#             # last round is mouse's turn
#             if not is_mouses_turn and any(mouse_pos == 0 for mouse_pos, _ in q):
#                 return 1
            
#             q2 = []
#             for mouse_pos, cat_pos in q:
#                 if is_mouses_turn:
#                     for nbr in edges[mouse_pos]:
#                         next_state = nbr, cat_pos
#                         if next_state in seen:
#                             continue
#                         q2.append(next_state)
#                         seen.add(next_state)
#                 else:
#                     for nbr in edges[cat_pos]:
#                         if nbr == 0:
#                             continue
#                         next_state = mouse_pos, nbr
#                         if next_state in seen:
#                             continue
#                         q2.append(next_state)
#                         seen.add(next_state)
#             q = q2
#             step += 1
#             is_mouses_turn = not is_mouses_turn
            
#         return 0
            
        
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn. Mouse will win if the mouse can find any winable node for the next step. If all the next step is winable for cats, then mouse lose.
                if any(search(t+1, x_nxt, y)==1 for x_nxt in graph[x]):return 1
                if all(search(t+1, x_nxt, y)==2 for x_nxt in graph[x]):return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, y_nxt)==2 for y_nxt in graph[y] if y_nxt!=0):return 2
                if all(search(t+1, x, y_nxt)==1 for y_nxt in graph[y] if y_nxt!=0):return 1
                return 0
        return search(0, 1, 2)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # encode = lambda p, c, m: (c << 7) | (m << 1) | p
        encode = lambda p, c, m: (p, c, m)
        decode = lambda c: (c & 0x1, c >> 7, (c >> 1) & 0x3f)
        n = len(graph)
        g = collections.defaultdict(list)
        outcomes = {}
        degrees = collections.Counter()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    status = encode(p, c, m)
                    if p == 0:
                        if c == m:
                            outcomes[status] = 1
                        elif m == 0:
                            outcomes[status] = -1
                    else:
                        if m == 0:
                            outcomes[status] = 1
                        elif c == m:
                            outcomes[status] = -1
                    if outcomes.get(status, 0):
                        continue
                    if p == 0:
                        for i in graph[c]:
                            if i == 0: continue
                            st = encode((p + 1) % 2, i, m)
                            g[st].append(status)
                            degrees[status] += 1
                    else:
                        for i in graph[m]:
                            st = encode((p + 1) % 2, c, i)
                            g[st].append(status)
                            degrees[status] += 1
        # for st, nei in g.items():
        #     print(st, nei)
        # print(outcomes)
        def dfs(status):
            visited.add(status)
            for st in g[status]:
                if st not in visited:
                    if outcomes[status] == -1:
                        outcomes[st] = 1
                    else:
                        degrees[st] -= 1
                        if degrees[st] == 0:
                            outcomes[st] = -1
                        else:
                            continue
                    dfs(st)
        visited = set()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    st = encode(p, c, m)
                    if outcomes.get(st, 0) and st not in visited:
                        dfs(st)
        
        o = outcomes.get(encode(1, 2, 1), 0)
        if o == -1:
            o = 2
        return o

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        encode = lambda p, c, m: (c << 7) | (m << 1) | p
        # encode = lambda p, c, m: (p, c, m)
        decode = lambda c: (c & 0x1, c >> 7, (c >> 1) & 0x3f)
        n = len(graph)
        g = collections.defaultdict(list)
        outcomes = {}
        degrees = collections.Counter()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    status = encode(p, c, m)
                    if p == 0:
                        if c == m:
                            outcomes[status] = 1
                        elif m == 0:
                            outcomes[status] = -1
                    else:
                        if m == 0:
                            outcomes[status] = 1
                        elif c == m:
                            outcomes[status] = -1
                    if outcomes.get(status, 0):
                        continue
                    if p == 0:
                        for i in graph[c]:
                            if i == 0: continue
                            st = encode((p + 1) % 2, i, m)
                            g[st].append(status)
                            degrees[status] += 1
                    else:
                        for i in graph[m]:
                            st = encode((p + 1) % 2, c, i)
                            g[st].append(status)
                            degrees[status] += 1
        # for st, nei in g.items():
        #     print(st, nei)
        # print(outcomes)
        def dfs(status):
            visited.add(status)
            for st in g[status]:
                if st not in visited:
                    if outcomes[status] == -1:
                        outcomes[st] = 1
                    else:
                        degrees[st] -= 1
                        if degrees[st] == 0:
                            outcomes[st] = -1
                        else:
                            continue
                    dfs(st)
        visited = set()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    st = encode(p, c, m)
                    if outcomes.get(st, 0) and st not in visited:
                        dfs(st)
        
        o = outcomes.get(encode(1, 2, 1), 0)
        if o == -1:
            o = 2
        return o

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y:
                dp[t][x][y] = 2
                return 2
            if x == 0:
                dp[t][x][y] = 1
                return 1
            if dp[t][x][y] != -1:return dp[t][x][y]
            if (t%2==0):# mouse's turn
                flag = True
                for i in range(len(graph[x])):
                    nxt = search(t+1, graph[x][i], y)
                    if nxt == 1:
                        dp[t][x][y] = 1
                        return 1
                    elif nxt!=2:
                        flag = False
                if flag:
                    dp[t][x][y] = 2
                    return 2
                dp[t][x][y] = 0
                return 0
            else:# cat's turn
                flag = True
                for i in range(len(graph[y])):
                    if graph[y][i]!=0:
                        nxt = search(t + 1, x, graph[y][i])
                        if nxt ==2:
                            dp[t][x][y] = 2
                            return 2
                        elif nxt != 1:flag=False
                if flag:
                    dp[t][x][y] = 1
                    return 1
                else:
                    dp[t][x][y] = 0
                    return 0
        n = len(graph)
        dp = [ [ [-1 for k in range(n)] for j in range(n)] for i in range(2*n)]
        return search(0, 1, 2)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        encode = lambda p, c, m: (c << 7) | (m << 1) | p
        # encode = lambda p, c, m: (p, c, m)
        decode = lambda c: (c & 0x1, c >> 7, (c >> 1) & 0x3f)
        n = len(graph)
        g = collections.defaultdict(list)
        outcomes = {}
        degrees = collections.Counter()
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    status = encode(p, c, m)
                    if p == 0:
                        if c == m:
                            outcomes[status] = 1
                        elif m == 0:
                            outcomes[status] = -1
                    else:
                        if m == 0:
                            outcomes[status] = 1
                        elif c == m:
                            outcomes[status] = -1
                    if outcomes.get(status, 0):
                        continue
                    if p == 0:
                        for i in graph[c]:
                            if i == 0: continue
                            st = encode((p + 1) % 2, i, m)
                            g[st].append(status)
                            degrees[status] += 1
                    else:
                        for i in graph[m]:
                            st = encode((p + 1) % 2, c, i)
                            g[st].append(status)
                            degrees[status] += 1
        # for st, nei in g.items():
        #     print(st, nei)
        # print(outcomes)
        def dfs(status):
            visited.add(status)
            if status == initial:
                return True
            for st in g[status]:
                if st not in visited:
                    if outcomes[status] == -1:
                        outcomes[st] = 1
                    else:
                        degrees[st] -= 1
                        if degrees[st] == 0:
                            outcomes[st] = -1
                        else:
                            continue
                    if dfs(st):
                        return True
        visited = set()
        initial = encode(1, 2, 1)
        for c in range(1, n):
            for m in range(n):
                for p in range(2):
                    st = encode(p, c, m)
                    if outcomes.get(st, 0) and st not in visited:
                        dfs(st)
        
        o = outcomes.get(encode(1, 2, 1), 0)
        if o == -1:
            o = 2
        return o

class Solution:
    def catMouseGame(self, graph):
        import functools
        n=len(graph)
        
        @lru_cache(None)
        def dp(t,x,y):
            if t==2*n:
                return 0
            if x==y:
                return 2
            if x==0:
                return 1
            if t%2==0:
                if any(dp(t+1,xn,y)==1 for xn in graph[x]):
                    return 1
                if all(dp(t+1,xn,y)==2 for xn in graph[x]):
                    return 2
                return 0
            else:
                if any(dp(t+1,x,yn)==2 for yn in graph[y] if yn!=0):
                    return 2
                if all(dp(t+1,x,yn)==1 for yn in graph[y] if yn!=0):
                    return 1
                return 0
        return dp(0,1,2)

from functools import lru_cache
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn. Mouse will win if the mouse can find any winable node for the next step. If all the next step is winable for cats, then mouse lose.
                if any(search(t+1, x_nxt, y)==1 for x_nxt in graph[x]):return 1
                if all(search(t+1, x_nxt, y)==2 for x_nxt in graph[x]):return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, y_nxt)==2 for y_nxt in graph[y] if y_nxt!=0):return 2
                if all(search(t+1, x, y_nxt)==1 for y_nxt in graph[y] if y_nxt!=0):return 1
                return 0
        return search(0, 1, 2)


class Solution:
    def catMouseGame(self, graph):
    
        from functools import lru_cache
        N=len(graph)
        @lru_cache(None)
        def search(t,x,y):
            if t==2*N:
                return 0
            if x==y:
                return 2
            if x==0:
                return 1
            if (t%2==0):
                if any(search(t+1,xn,y)==1 for xn in graph[x]):
                    return 1
                if all(search(t+1,xn,y)==2 for xn in graph[x]):
                    return 2
                return 0
            else:
                if all(search(t+1,x,yn)==1 for yn in graph[y] if yn!=0):
                    return 1
                if any(search(t+1,x,yn)==2 for yn in graph[y] if yn!=0):
                    return 2
                return 0
        return search(0,1,2)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        dp = {}
        n = len(graph)

        def dfs(im, ic, nmove):
            mouse_move = nmove % 2
            if im == 0:
                return 1
            if im == ic:
                return 2
            if nmove >= 2 * n + 1:
                dp[(im, ic, nmove)] = 0
                return 0
            if (im, ic, nmove) in dp:
                return dp[(im, ic, nmove)]
                        
            wins = [0, 0, 0]
            ret = None
            if mouse_move:
                for nxt in graph[im]:    
                    idx = dfs(nxt, ic, nmove + 1)
                    wins[idx] += 1
                    if idx == 1:
                        break
                if wins[1] > 0:
                    ret = 1
                elif wins[0] > 0:
                    ret = 0
                else:
                    ret = 2
            else:
                for nxt in graph[ic]:
                    if nxt != 0:
                        idx = dfs(im, nxt, nmove + 1)
                        wins[idx] += 1
                        if idx == 2:
                            break
                
                if wins[2] > 0:
                    ret = 2
                elif wins[0] > 0:
                    ret = 0
                else:
                    ret = 1
            dp[(im, ic, nmove)] = ret
            return ret
        
        res = dfs(1, 2, 1)
        return res


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y:
                dp[t][x][y] = 2
                return 2
            if x == 0:
                dp[t][x][y] = 1
                return 1
            if dp[t][x][y] != -1:return dp[t][x][y]
            if (t%2==0):# mouse's turn
                flag = True
                for i in range(len(graph[x])):
                    nxt = search(t+1, graph[x][i], y)
                    if nxt == 1:
                        dp[t][x][y] = 1
                        return 1
                    elif nxt!=2:
                        flag = False
                if flag:
                    dp[t][x][y] = 2
                    return 2
                dp[t][x][y] = 0
                return 0
            else:# cat's turn
                flag = True
                for i in range(len(graph[y])):
                    if graph[y][i]!=0:
                        nxt = search(t + 1, x, graph[y][i])
                        if nxt ==2:
                            dp[t][x][y] = 2
                            return 2
                        elif nxt != 1:flag=False
                if flag:
                    dp[t][x][y] = 1
                    return 1
                else:
                    dp[t][x][y] = 0
                    return 0
        n = len(graph)
        dp = [ [ [-1 for k in range(n)] for j in range(n)] for i in range(2*n)]
        return search(0, 1, 2)


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        N = len(graph)
        # dp[t][i][j] := game outcome when at time t, mouse at i, cat at j
        ## 0: draw, 1: mouse wins, 2: cat wins
        dp = [[[-1]*N for _ in range(N)] for m in range(2*N)]
        
        for m in range(2*N):
            for i in range(N):
                dp[m][i][i] = 2 # win by cat
                dp[m][0][i] = 1 # win by mouse
        # dp = 0 when m==2N
        
        def _search(t, x, y):
            # time, mouse pos, cat pos
            if t==2*N: return 0
            if dp[t][x][y]!=-1: return dp[t][x][y]
            
            if t%2==0: # mouse
                winByCat = True
                for i in graph[x]:
                    nxt = _search(t+1, i, y)
                    if nxt==1:
                        dp[t][x][y] = 1
                        return 1
                    if nxt!=2:
                        winByCat = False
                if winByCat:
                    dp[t][x][y] = 2
                    return 2
                else:
                    dp[t][x][y] = 0
                    return 0
            else: # cat
                winByMouse = True
                for i in graph[y]:
                    if i!=0: # cat cannot be at the hole -- 0
                        nxt = _search(t+1, x, i)
                        if nxt==2:
                            dp[t][x][y] = 2
                            return 2
                        if nxt!=1:
                            winByMouse = False
                if winByMouse:
                    dp[t][x][y] = 1
                    return 1
        
        
        return _search(0, 1, 2)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn
                if any(search(t+1, graph[x][i], y)==1 for i in range(len(graph[x]))):
                    return 1
                if all(search(t+1, graph[x][i], y)==2 for i in range(len(graph[x]))):
                    return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, graph[y][i])==2 for i in range(len(graph[y])) if graph[y][i]!=0):
                    return 2
                if all(search(t + 1, x, graph[y][i])==1 for i in range(len(graph[y])) if graph[y][i]!=0): 
                    return 1
                return 0
        return search(0, 1, 2)


class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            return mem[mouse][cat][turn]
        def play(mouse, cat, turn):
            if mem[mouse][cat][turn]!=-1: return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if turn % 2:
                ans = 2
                for node in graph[mouse]:
                    if node == cat: continue
                    if node == 0: return storeRet(mouse,cat,turn,1)
                    res = play(node, cat, turn+1)
                    if res == 1: return storeRet(mouse,cat,turn,1)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
            else:
                ans = 1
                for node in graph[cat]:
                    if node == 0: continue
                    if node == mouse: return storeRet(mouse,cat,turn,2)
                    res = play(mouse, node, turn+1)
                    if res == 2: return storeRet(mouse,cat,turn,2)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
        return play(1,2,1)

class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            return mem[mouse][cat][turn]
        def play(mouse, cat, turn):
            #print(f'turn {turn} mouse {mouse} cat {cat}')
            if mem[mouse][cat][turn]!=-1:
              #print(f'{mouse} {cat} {turn} already calc: {mem[mouse][cat][turn]}')
              return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if turn % 2:
                #print('mouse turn')
                ans = 2
                for node in graph[mouse]:
                    #print(f'mouse check {node}')
                    if node == cat: continue
                    if node == 0: return storeRet(mouse,cat,turn,1)
                    res = play(node, cat, turn+1)
                    if res == 1: return storeRet(mouse,cat,turn,1)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
            else:
                #print('cat turn')
                ans = 1
                for node in graph[cat]:
                    #print(f'cat check {node}')
                    if node == 0: continue
                    if node == mouse: return storeRet(mouse,cat,turn,2)
                    res = play(mouse, node, turn+1)
                    if res == 2: return storeRet(mouse,cat,turn,2)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
        return play(1,2,1)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn. Mouse will win if the mouse can find any winable node for the next step. If all the next step is winable for cats, then mouse lose.
                if any(search(t+1, x_nxt, y)==1 for x_nxt in graph[x]):return 1
                if all(search(t+1, x_nxt, y)==2 for x_nxt in graph[x]):return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, y_nxt)==2 for y_nxt in graph[y] if y_nxt!=0):return 2
                if all(search(t+1, x, y_nxt)==1 for y_nxt in graph[y] if y_nxt!=0):return 1
                return 0
            
        return search(0, 1, 2)

class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            return mem[mouse][cat][turn]
        def play(mouse, cat, turn):
            if mem[mouse][cat][turn]!=-1: return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if not turn % 2:
                ans = 2
                for node in graph[mouse]:
                    if node == cat: continue
                    if node == 0: return storeRet(mouse,cat,turn,1)
                    res = play(node, cat, turn+1)
                    if res == 1: return storeRet(mouse,cat,turn,1)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
            else:
                ans = 1
                for node in graph[cat]:
                    if node == 0: continue
                    if node == mouse: return storeRet(mouse,cat,turn,2)
                    res = play(mouse, node, turn+1)
                    if res == 2: return storeRet(mouse,cat,turn,2)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            return mem[mouse][cat][turn]
        mouseWin = lambda m,c,t:storeRet(m,c,t,1)
        catWin = lambda m,c,t:storeRet(m,c,t,2)
        def play(mouse, cat, turn):
            if mem[mouse][cat][turn]!=-1: return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if not turn % 2:
                ans = 2
                for node in graph[mouse]:
                    if node == 0: return mouseWin(mouse,cat,turn)
                    if node == cat: continue
                    res = play(node, cat, turn+1)
                    if res == 1: return mouseWin(mouse,cat,turn)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
            else:
                ans = 1
                for node in graph[cat]:
                    if node == mouse: return catWin(mouse,cat,turn)
                    if node == 0: continue
                    res = play(mouse, node, turn+1)
                    if res == 2: return catWin(mouse,cat,turn)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, g):
        mem = [[[-1 for i in range(1+2*len(g))] for i in range(1+2*len(g))] for i in range(2*len(g))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        draw, mouseWin, catWin = lambda m,c,t:storeRet(m,c,t,0),lambda m,c,t:storeRet(m,c,t,1),lambda m,c,t:storeRet(m,c,t,2)
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # already visited this game state
            if t >= 2*len(g): return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in g[m]:
                    if n == 0: return mouseWin(m,c,t)
                    if n == c: continue
                    nextTurn = play(n, c, t+1)
                    if nextTurn == 1: return mouseWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in g[c]:
                    if n == m: return catWin(m,c,t)
                    if n == 0: continue
                    nextTurn = play(m, n, t+1)
                    if nextTurn == 2: return catWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            return mem[mouse][cat][turn]
        mouseWin = lambda m,c,t:storeRet(m,c,t,1)
        catWin = lambda m,c,t:storeRet(m,c,t,2)
        draw = lambda m,c,t:storeRet(m,c,t,0)
        def play(mouse, cat, turn):
            if mem[mouse][cat][turn]!=-1: return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if not turn % 2:
                drawFound = False
                for node in graph[mouse]:
                    if node == 0: return mouseWin(mouse,cat,turn)
                    if node == cat: continue
                    res = play(node, cat, turn+1)
                    if res == 1: return mouseWin(mouse,cat,turn)
                    if res == 0: drawFound = True
                return draw(mouse,cat,turn) if drawFound else catWin(mouse,cat,turn)
            else:
                drawFound=False
                for node in graph[cat]:
                    if node == mouse: return catWin(mouse,cat,turn)
                    if node == 0: continue
                    res = play(mouse, node, turn+1)
                    if res == 2: return catWin(mouse,cat,turn)
                    if res == 0: drawFound = True
                return draw(mouse,cat,turn) if drawFound else mouseWin(mouse,cat,turn)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, g):
        mem = [[[-1 for i in range(1+2*len(g))] for i in range(1+2*len(g))] for i in range(2*len(g))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        mouseWin = lambda m,c,t:storeRet(m,c,t,1)
        catWin = lambda m,c,t:storeRet(m,c,t,2)
        draw = lambda m,c,t:storeRet(m,c,t,0)
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # already visited this game state
            if t >= 2*len(g): return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in g[m]:
                    if n == 0: return mouseWin(m,c,t)
                    if n == c: continue
                    nextTurn = play(n, c, t+1)
                    if nextTurn == 1: return mouseWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in g[c]:
                    if n == m: return catWin(m,c,t)
                    if n == 0: continue
                    nextTurn = play(m, n, t+1)
                    if nextTurn == 2: return catWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, g):
        mem = [[[-1 for i in range(1+2*len(g))] for i in range(1+2*len(g))] for i in range(2*len(g))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        draw, mouseWin, catWin = lambda m,c,t:storeRet(m,c,t,0),lambda m,c,t:storeRet(m,c,t,1),lambda m,c,t:storeRet(m,c,t,2)
        HOLE = 0
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # return cached
            if t >= 2*len(g): return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in g[m]:
                    if n == HOLE: return mouseWin(m,c,t)
                    if n == c: continue
                    nextTurn = play(n, c, t+1)
                    if nextTurn == 1: return mouseWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in g[c]:
                    if n == m: return catWin(m,c,t)
                    if n == HOLE: continue
                    nextTurn = play(m, n, t+1)
                    if nextTurn == 2: return catWin(m,c,t)
                    if nextTurn == 0: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, g):
        mem = [[[-1 for i in range(1+2*len(g))] for i in range(1+2*len(g))] for i in range(2*len(g))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        mouseWin = lambda m,c,t:storeRet(m,c,t,1)
        catWin = lambda m,c,t:storeRet(m,c,t,2)
        draw = lambda m,c,t:storeRet(m,c,t,0)
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # already visited this game state
            if t >= len(g)*2: return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in g[m]:
                    if n == 0: return mouseWin(m,c,t)
                    if n == c: continue
                    res = play(n, c, t+1)
                    if res == 1: return mouseWin(m,c,t)
                    if res == 0: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in g[c]:
                    if n == m: return catWin(m,c,t)
                    if n == 0: continue
                    res = play(m, n, t+1)
                    if res == 2: return catWin(m,c,t)
                    if res == 0: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(1+2*len(graph))] for i in range(1+2*len(graph))] for i in range(2*len(graph))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        mouseWin = lambda m,c,t:storeRet(m,c,t,1)
        catWin = lambda m,c,t:storeRet(m,c,t,2)
        draw = lambda m,c,t:storeRet(m,c,t,0)
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # already visited this game state
            if t >= len(graph)*2: return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in graph[m]:
                    if n == 0: return mouseWin(m,c,t)
                    if n == c: continue
                    res = play(n, c, t+1)
                    if res == 1: return mouseWin(m,c,t)
                    if res == 0: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in graph[c]:
                    if n == m: return catWin(m,c,t)
                    if n == 0: continue
                    res = play(m, n, t+1)
                    if res == 2: return catWin(m,c,t)
                    if res == 0: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

from collections import deque
class Solution:
    def catMouseGame(self, graph):
      
        arr = [[[0]*2 for j in range(55)] for i in range(55)]
        q=deque()
        for i in range(1,len(graph)):
            arr[i][i][0],arr[i][i][1]=2,2
            arr[i][0][0],arr[i][0][1]=1,1
            q.append((i,0,0))
            q.append((i,0,1))
            q.append((i,i,0))
            q.append((i,i,1))
        while q:
            c,m,turn = q.popleft()
            s = arr[c][m][turn]
            if turn==0:
                
                for pre_move in graph[m]:
                    if arr[c][pre_move][1]!=0:
                        continue
                    if s==1:
                        arr[c][pre_move][1]=1
                        q.append((c,pre_move,1))
                    elif s==2:
                        cat_win=True
                        for nex_move in graph[pre_move]:
                            if arr[c][nex_move][0]!=2:
                                cat_win=False
                                break
                        if cat_win:
                            arr[c][pre_move][1]=2
                            q.append((c,pre_move,1))
            else:
                for pre_move in graph[c]:
                    if arr[pre_move][m][0]!=0:
                        continue
                    if pre_move!=0:
                        if s==2:
                            arr[pre_move][m][0]=2
                            q.append((pre_move,m,0))
                        elif s==1:
                            mouse_win=True
                            for nex_move in graph[pre_move]:
                                if nex_move!=0:
                                    if arr[nex_move][m][1]!=1:
                                        mouse_win=False
                                        break
                            if mouse_win:
                                arr[pre_move][m][0]=1
                                q.append((pre_move,m,0))
        return arr[2][1][1]

class Solution:
    def catMouseGame(self, g):
        mem = [[[-1 for i in range(1+2*len(g))] for i in range(1+2*len(g))] for i in range(2*len(g))]
        def storeRet(m,c,t,v):
            mem[m][c][t] = v
            return mem[m][c][t]
        HOLE, DRAW, MOUSE_WIN, CAT_WIN = 0, 0, 1, 2
        draw, mouseWin, catWin = lambda m,c,t:storeRet(m,c,t,DRAW),lambda m,c,t:storeRet(m,c,t,MOUSE_WIN),lambda m,c,t:storeRet(m,c,t,CAT_WIN)
        
        def play(m, c, t):
            if mem[m][c][t]!=-1: return mem[m][c][t] # return cached
            if t >= 2*len(g): return 0 # repeated states
            if not t % 2: # mouse turn
                drawFound = False
                for n in g[m]:
                    if n == HOLE: return mouseWin(m,c,t)
                    if n == c: continue
                    nextTurn = play(n, c, t+1)
                    if nextTurn == MOUSE_WIN: return mouseWin(m,c,t)
                    if nextTurn == DRAW: drawFound = True
                return draw(m,c,t) if drawFound else catWin(m,c,t)
            else: # cat turn
                drawFound=False
                for n in g[c]:
                    if n == m: return catWin(m,c,t)
                    if n == HOLE: continue
                    nextTurn = play(m, n, t+1)
                    if nextTurn == CAT_WIN: return catWin(m,c,t)
                    if nextTurn == DRAW: drawFound = True
                return draw(m,c,t) if drawFound else mouseWin(m,c,t)
        return play(1,2,0)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # return 1
        n = len(graph)
        states = [[[0, 0] for _ in range(n)] for _ in range(n)]  # [mouse][cat][whose_turn (m/c)]
        for i in range(1, n):
            # mosue turn is 0, cat is 1
            states[0][i][0] = -1
            states[0][i][1] = -1
            states[i][i][0] = 1
            states[i][i][1] = 1
        
        # cnt = 0
        get_updated = False
        for _ in range(2 * n):
            
            get_updated = False
            
            for mouse in range(1, n):
                for cat in range(1, n):
                    for turn in range(2):
                        if mouse != cat and mouse != 0:
                            if turn == 0:
                                adj = graph[mouse]
                                res = float('inf')
                                for node in adj:
                                    res = min(res, states[node][cat][1])
                                    # cnt += 1
                                
                                if states[mouse][cat][turn] != res:
                                    get_updated = True
                                    
                                states[mouse][cat][turn] = res
                            else:
                                adj = graph[cat]
                                res = float('-inf')
                                for node in adj:
                                    if node != 0:
                                        res = max(res, states[mouse][node][0])
                                        # cnt += 1
                                    
                                if states[mouse][cat][turn] != res:
                                    get_updated = True
                                    
                                    states[mouse][cat][turn] = res
            if not get_updated:
                break
        
        # print(states[3][3][0])
        # print(cnt)
        
        res = states[1][2][0]
        # res = self.play(1, 2, 0, graph, states)
        if res < 0:
            return 1
        if res > 0:
            return 2
        return 0


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        # return 1
        n = len(graph)
        states = [[[0, 0] for _ in range(n)] for _ in range(n)]  # [mouse][cat][whose_turn (m/c)]
        for i in range(1, n):
            # mosue turn is 0, cat is 1
            states[0][i][0] = -1
            states[0][i][1] = -1
            states[i][i][0] = 1
            states[i][i][1] = 1
        
        get_updated = False
        for _ in range(2 * n):
            
            get_updated = False
            
            for mouse in range(1, n):
                for cat in range(1, n):
                    for turn in range(2):
                        if mouse != cat and mouse != 0:
                            if turn == 0:
                                adj = graph[mouse]
                                res = float('inf')
                                for node in adj:
                                    res = min(res, states[node][cat][1])
                                
                                if states[mouse][cat][turn] != res:
                                    get_updated = True
                                    
                                states[mouse][cat][turn] = res
                            else:
                                adj = graph[cat]
                                res = float('-inf')
                                for node in adj:
                                    if node != 0:
                                        res = max(res, states[mouse][node][0])
                                    
                                if states[mouse][cat][turn] != res:
                                    get_updated = True
                                    
                                    states[mouse][cat][turn] = res
            if not get_updated:
                break

        res = states[1][2][0]
        if res < 0:
            return 1
        if res > 0:
            return 2
        return 0


class Solution:
    def catMouseGame(self, g: List[List[int]]) -> int:
        # observations:
        # we can represent the game state with the triplet (mouse cat turn).
        # (_ 0 _) is illegal.
        # (0 _ _) = 1 (mouse victory).
        # (x x _) = 2 (cat victory).
        # if any possible move leads to win, current state is win:
        # * (m c c) = 1 => (m' c m) = 1 for m' in g[m].
        # * (m c m) = 2 => (m c' c) = 2 for c' in g[c].
        # (m c m) = 1 and c not in g[m] => (m c c) = 1.
        # if all possible moves lead to loss, current state is loss.
        # * (m c m) = 1, for c' in g[c], if all((m c'' m) = 1 for c'' in g[c']) => (m c' c) = 1
        # return (1 2 m). return once we know its value.

        n = len(g)
        s = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        q = deque()

        def sq(m, c, t, v):
            if s[m][c][t] == 0:
                q.append((m, c, t))
                s[m][c][t] = v

        # approach:

        # set and enqueue initial known states.
        for m in range(n):
            for t in range(2):
                sq(m, 0, t, -1)
        for c in range(n):
            for t in range(2):
                sq(0, c, t, 1)
        for x in range(n):
            for t in range(2):
                sq(x, x, t, 2)

        # while queue:
        while q:
            # pop state.
            m, c, t = state = q.popleft()
            # apply production rules. for each unencountered resultant state, set and enqueue.
            if t == 1 and s[m][c][t] == 1:
                for m_ in g[m]:
                    sq(m_, c, 0, 1)

            if t == 0 and s[m][c][t] == 2:
                for c_ in g[c]:
                    sq(m, c_, 1, 2)

            # if t == 0 and s[m][c][t] == 1 and c not in g[m]:
            #     sq(m, c, 1, 1)

            if t == 0 and s[m][c][t] == 1:
                for c_ in g[c]:
                    if all(s[m][c__][0] in (-1, 1) for c__ in g[c_]):
                        sq(m, c_, 1, 1)

            if t == 1 and s[m][c][t] == 2:
                for m_ in g[m]:
                    if all(s[m__][c][1] in (-1, 2) for m__ in g[m_]):
                        sq(m_, c, 0, 2)

        # everything else is a draw.

        # return state[1,2,m].
        return s[1][2][0]


class Solution:
    def catMouseGame(self, graph):
        mem = [[[-1 for i in range(3*len(graph))] for i in range(3*len(graph))] for i in range(2*len(graph))]
        def storeRet(mouse,cat,turn,value):
            mem[mouse][cat][turn] = value
            #print(f'store {value} for {mouse} {cat} {turn}')
            return mem[mouse][cat][turn]
        def play(mouse, cat, turn):
            #print(f'turn {turn} mouse {mouse} cat {cat}')
            if mem[mouse][cat][turn]!=-1:
              #print(f'{mouse} {cat} {turn} already calc: {mem[mouse][cat][turn]}')
              return mem[mouse][cat][turn]
            if turn >= len(graph)*2: return 0
            if turn % 2:
                #print('mouse turn')
                ans = 2
                for node in graph[mouse]:
                    #print(f'mouse check {node}')
                    if node == cat: continue
                    if node == 0: return storeRet(mouse,cat,turn,1)
                    res = play(node, cat, turn+1)
                    if res == 1: return storeRet(mouse,cat,turn,1)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
            else:
                #print('cat turn')
                ans = 1
                for node in graph[cat]:
                    #print(f'cat check {node}')
                    if node == 0: continue
                    if node == mouse: return storeRet(mouse,cat,turn,2)
                    res = play(mouse, node, turn+1)
                    if res == 2: return storeRet(mouse,cat,turn,2)
                    if res == 0: ans = 0
                return storeRet(mouse,cat,turn,ans)
        return play(1,2,1)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        mouse, cat = 1, 2
        node = defaultdict(int)
        graphLen = len(graph)
        # key = (m0, c0, t)
        stack = [] 
        for l in graph[0]:
            for ci in range(1, graphLen):
                if ci != l:
                    node[(l, ci, mouse)] = mouse
                    stack.append((l, ci, mouse, mouse))
        for i in range(1, graphLen):
            for j in graph[i]:
                if j != 0:
                    node[(i, j, cat)] = cat
                    stack.append((i, j, cat, cat))
            node[(i, i, cat)] = cat
            node[(i, i, mouse)] = cat
            stack.append((i, i, cat, cat))
            stack.append((i, i, mouse, cat))
            
        degree = {}
        for i in range(graphLen):
            for j in range(graphLen):
                if i != j:
                    if (i, j, mouse) not in stack:
                        degree[(i, j, mouse)] = len(graph[i])
                    if (i, j, cat) not in stack:
                        degree[(i, j, cat)] = len(graph[j]) - (1 if 0 in graph[j] else 0)
        
        while stack:
            m0, c0, t0, w = stack.pop(0)
            if t0 == mouse:
                if w == cat:
                    for move in graph[c0]:
                        if move != 0 and (m0, move, cat) not in node:
                            node[(m0, move, cat)] = cat
                            stack.append((m0, move, cat, cat))
                else:
                    for move in graph[c0]:    
                        if move != 0 and (m0, move, cat) not in node:
                            degree[(m0, move, cat)] -= 1
                            if degree[(m0, move, cat)] == 0:
                                node[(m0, move, cat)] = mouse
                                stack.append((m0, move, cat, mouse))
            else:
                if w == mouse:
                    for move in graph[m0]:
                        if (move, c0, mouse) not in node:
                            node[(move, c0, mouse)] = mouse
                            stack.append((move, c0, mouse, mouse))
                else:
                    for move in graph[m0]:    
                        if (move, c0, mouse) not in node:
                            degree[(move, c0, mouse)] -= 1
                            if degree[(move, c0, mouse)] == 0:
                                node[(move, c0, mouse)] = cat
                                stack.append((move, c0, mouse, cat))
        # print(node)
        return node[(1, 2, mouse)]
                            


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        mouse, cat = 1, 2
        node = defaultdict(int)
        graphLen = len(graph)
        # key = (m0, c0, t)
        stack = deque([]) 
        for l in graph[0]:
            for ci in range(1, graphLen):
                if ci != l:
                    node[(l, ci, mouse)] = mouse
                    stack.append((l, ci, mouse, mouse))
        for i in range(1, graphLen):
            for j in graph[i]:
                if j != 0:
                    node[(i, j, cat)] = cat
                    stack.append((i, j, cat, cat))
            node[(i, i, cat)] = cat
            node[(i, i, mouse)] = cat
            stack.append((i, i, cat, cat))
            stack.append((i, i, mouse, cat))
            
        degree = {}
        for i in range(graphLen):
            for j in range(graphLen):
                if i != j:
                    if (i, j, mouse) not in stack:
                        degree[(i, j, mouse)] = len(graph[i])
                    if (i, j, cat) not in stack:
                        degree[(i, j, cat)] = len(graph[j]) - (1 if 0 in graph[j] else 0)
        
        while stack:
            m0, c0, t0, w = stack.popleft()
            if t0 == mouse:
                if w == cat:
                    for move in graph[c0]:
                        if move != 0 and (m0, move, cat) not in node:
                            node[(m0, move, cat)] = cat
                            stack.append((m0, move, cat, cat))
                else:
                    for move in graph[c0]:    
                        if move != 0 and (m0, move, cat) not in node:
                            degree[(m0, move, cat)] -= 1
                            if degree[(m0, move, cat)] == 0:
                                node[(m0, move, cat)] = mouse
                                stack.append((m0, move, cat, mouse))
            else:
                if w == mouse:
                    for move in graph[m0]:
                        if (move, c0, mouse) not in node:
                            node[(move, c0, mouse)] = mouse
                            stack.append((move, c0, mouse, mouse))
                else:
                    for move in graph[m0]:    
                        if (move, c0, mouse) not in node:
                            degree[(move, c0, mouse)] -= 1
                            if degree[(move, c0, mouse)] == 0:
                                node[(move, c0, mouse)] = cat
                                stack.append((move, c0, mouse, cat))
        # print(node)
        return node[(1, 2, mouse)]