Circle and Marble

Adi and Putri have been together for years, and Adi is ready to propose. Putri does not want to make it easy. She asks Adi to play a game with her, and she will marry him if he wins.

Putri drew one circle and put some marbles inside it. Then she drew a second circle, put some marbles inside it, and drew one arrow from the first circle to the new one. Then she drew a third circle, put some marbles inside it, and drew one arrow from one of the circles already on the paper to the new one. She repeated this until she had drawn $N$ circles. Some circles may hold no marbles. No two circles overlap and no circle sits inside another.

The two players move alternately. On your turn you pick one circle, take exactly one marble out of it, and move that marble to one of the circles that the arrows leaving the chosen circle point to. Whoever cannot move loses.

A circle with no outgoing arrow cannot be picked. Moving the marble to another circle is mandatory, so a circle the marble cannot leave is not a legal choice. A circle holding no marble cannot be picked either. The same rules bind both players.

If both players play optimally, the starting configuration alone decides the winner. Putri lets Adi choose who moves first. Given the starting configuration, decide whether Adi should move first or second in order to win. Putri plays optimally, so she wins whenever she gets the chance.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case begins with a line containing $N$, the number of circles Putri drew ($3 \le N \le 20000$). The circles are numbered $1$ to $N$ in the order she drew them.

The second line contains $N$ integers $M_1, M_2, \ldots, M_N$, where $M_i$ is the number of marbles in circle $i$ ($0 \le M_i \le 1000000$).

The third line contains $N$ integers $P_1, P_2, \ldots, P_N$, where $P_i$ is the circle that the arrow pointing at circle $i$ starts from ($1 \le P_i < i \le N$). Circle $1$ was drawn first, so no arrow points at it and $P_1$ is always $0$.

For each test case, print one line in the form Case #X: Y. $X$ is the test case number starting from $1$, followed by a single space. $Y$ is first if Adi should take the first move to win, or second if he should move second.

These notations make the walkthrough shorter.

• move(a, b) means taking one marble out of circle $a$ and moving it to circle $b$.
• $\langle m_1, m_2, m_3, \ldots \rangle$ lists the number of marbles in circle $1$, circle $2$, circle $3$, and so on.

In the first case of the example input, the first player plays move(2, 3) and reaches $\langle 1, 0, 3 \rangle$. The second player has nothing but move(1, 2), reaching $\langle 0, 1, 3 \rangle$. The first player plays move(2, 3) again, reaches $\langle 0, 0, 4 \rangle$, and the second player cannot move.

In the second case, the first player loses whatever he plays. He has two moves.

• move(1, 2) reaches $\langle 0, 3, 2 \rangle$. The two players then take turns moving marbles from circle $2$ to circle $3$, and the second player wins.
• move(2, 3) reaches $\langle 1, 1, 3 \rangle$. The second player answers with move(2, 3) to reach $\langle 1, 0, 4 \rangle$. The first player has nothing but move(1, 2), and the second player ends the game with move(2, 3).

So Adi should be the second player in this configuration.

In the third case, the first player plays move(1, 2) and reaches $\langle 0, 2, 2, 3 \rangle$. The second player has nothing but move(3, 4), reaching $\langle 0, 2, 1, 4 \rangle$. The first player moves the last marble of circle $3$ to circle $4$, and the second player cannot move.