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: MEDIUM
Tags: Graph algorithms

Directed graphs

Dynamic programming

Game theory

Mathematics
Skill types: Dynamic programming

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)

		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 = {}
		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])
		queue = collections.deque([])
		for cat in range(N):
			for turn in [MOUSE, CAT]:
				mouse = 0
				colors[mouse, cat, turn] = MOUSE
				queue.append((mouse, cat, turn, MOUSE))
				if cat > 0:
					mouse = cat
					colors[mouse, cat, turn] = CAT
					queue.append((mouse, cat, turn, CAT))
		while queue:
			(mouse, cat, turn, color) = queue.popleft()
			for (prev_mouse, prev_cat, prev_turn) in parents(mouse, cat, turn):
				if colors[prev_mouse, prev_cat, prev_turn] is DRAW:
					if prev_turn == color:
						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:
						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]


class Solution:

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

		@lru_cache(None)
		def move(cat, mouse, t):
			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)


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)]
		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 = []
		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:
				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))
			elif 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:
		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
			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:
					continue
				s2 = (1, node, s[2])
				if s2 in visited:
					hold_move += 1
					continue
				ret = dfs(s2, visited)
				if ret == 1:
					return 1
				if ret == 0:
					hold_move += 1
			if hold_move:
				return 0
			else:
				return 2

		def dfs_c(s, visited):
			if s[1] in graph[s[2]]:
				return 2
			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
				if ret == 0:
					hold_move += 1
			if hold_move:
				return 0
			else:
				return 1
		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)

		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 color[i2, j2, t2] is DRAW:
					if t2 == c:
						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)

		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:
		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
		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()
			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)
			if s[1][2][0]:
				return s[1][2][0]
		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:
						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]


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:
		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:

	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]:
				if nxt == cat:
					continue
				tmp = move(cat, nxt, False)
				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 == 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:
						yield (m, c2, 3 - t)
			if t == CAT:
				for m2 in graph[m]:
					yield (m2, c, 3 - t)
		(color, degree) = (collections.defaultdict(int), {})
		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 (m2, c2, t2) in parents(m, c, t):
				if color[m2, c2, t2] is DRAW:
					if t2 == col:
						color[m2, c2, t2] = col
						que.append((m2, c2, t2))
					else:
						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:
		(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
		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()
			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)
			if s[1][2][MTURN]:
				return s[1][2][MTURN]
		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]


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)
		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
				dp[m][0][i] = 1

		def _search(t, x, y):
			if t == 2 * N:
				return 0
			if dp[t][x][y] != -1:
				return dp[t][x][y]
			if t % 2 == 0:
				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:
				winByMouse = True
				for i in graph[y]:
					if i != 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:
			if m == 0:
				return 1
			elif m == c:
				return 2
			elif time >= 50:
				return 0
			if turn == 0:
				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
		decode = lambda c: (c & 1, c >> 7, c >> 1 & 63)
		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
					elif 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

		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
			elif 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:
		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:
		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
			(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:
						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:

	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)

		@lru_cache(None)
		def can_win(cat_pos, mouse_pos, remaining_moves, is_cats_turn):
			if mouse_pos == 0:
				if is_cats_turn:
					return -1
				return 1
			if cat_pos == mouse_pos:
				if is_cats_turn:
					return 1
				return -1
			if remaining_moves == 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))
			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:

		@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:
				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:
				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):
		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:
				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:
				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:

		@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:
				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:
				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]
		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]
			if t >= 2 * len(g):
				return 0
			if not t % 2:
				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:
				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)


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, graph: List[List[int]]) -> int:
		n = len(graph)
		states = [[[0, 0] for _ in range(n)] for _ in range(n)]
		for i in range(1, n):
			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, graph: List[List[int]]) -> int:
		(mouse, cat) = (1, 2)
		node = defaultdict(int)
		graphLen = len(graph)
		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))
			elif 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))
		return node[1, 2, mouse]