class Solution {

    static final int MOUSE_WIN = 1;

    static final int CAT_WIN = 2;

    static final int DRAW = 0;

    int n;

    int[][][] dp;   // dp[mouse][cat][turns]：表示在经历turns轮次，老鼠在mouse位置，猫在cat位置时游戏的状态

    int[][] graph;

    public int catMouseGame(int[][] graph) {

        this.n = graph.length;

        this.graph = graph;

        this.dp = new int[n][n][n*2];

        // 初始化

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                Arrays.fill(dp[i][j], -1);

            }

        }

        return getResult(1, 2, 0);

    }

    private int getResult(int mouse, int cat, int turns) {

        if (turns == 2*n) {

            return DRAW;

        }

        // 未分出比赛状态

        if (dp[mouse][cat][turns] == -1) {

            if (mouse == 0) {

                dp[mouse][cat][turns] = MOUSE_WIN;

            } else if (mouse == cat) {

                dp[mouse][cat][turns] = CAT_WIN;

            } else {

                getNextResult(mouse, cat, turns);

            }

        }

        return dp[mouse][cat][turns];

    }

    private void getNextResult(int mouse, int cat, int turns) {

        // turns 为偶数时，老鼠先走

        int curMove = turns % 2 == 0? mouse: cat;

        int notHopeResult = curMove == mouse?  CAT_WIN: MOUSE_WIN;

        int result = notHopeResult;

        int[] nextNodes = graph[curMove];

        for (int next: nextNodes) {

            if (curMove == cat && next == 0) continue;  // 猫无法移动到0

            int nextCat = curMove == cat? next: cat;

            int nextMouse = curMove == mouse? next: mouse;

            int nextResult = getResult(nextMouse, nextCat, turns + 1);

            if (nextResult != notHopeResult) {  // 对于老鼠来说：他不希望nextResult为猫赢

                result = nextResult;

                if (result != DRAW) break;  // 已经分出胜负，则无需再比赛；若为平局则一直试探下一个next

            }

        }

        dp[mouse][cat][turns] = result;

    }

}