월간 훈수회

pjshwa와 nadori가 들판에서 게임을 하고 있다.

게임판은 정점이 $N$개인 함수형 그래프이다. 각 플레이어는 말을 하나씩 가지고 있고, 각 말은 그래프의 정점 중 하나에 존재한다. 한 정점에 여러 말이 존재할 수 있다.

두 플레이어는 번갈아 가며 본인의 차례에 아래의 행동 중 하나를 골라 수행한다. 본인 차례에 더 이상 행동을 할 수 없는 플레이어는 패배한다.

• 정점 $x$ 및 정점 $x$와 직접 연결된 모든 간선을 삭제한다. 정점 $x$에 플레이어의 말이 존재하면 안 된다.
• 현재 정점의 나가는 간선을 타고 이웃한 정점으로 이동한다.

게임을 공정하게 하기 위해 한 플레이어가 게임판과 말의 위치를 정한다. 다른 플레이어는 게임판과 말의 위치를 확인한 후 선공 혹은 후공을 선택한다. 그 후 게임을 진행한다. 단, 게임이 너무 길어져 지루해지는 것을 방지하기 위해, 후공 플레이어가 $10^{100}$ 번째 행동을 하고 나서도 게임이 끝나지 않았다면 무승부로 한다.

IBory는 심심할 때면 들판을 찾아가 훈수를 둔다. 오늘도 어김없이 훈수를 두러 왔는데 아뿔싸! 게임 도중이 아니었다. 평소 IBory의 훈수로 화가 난 nadori는 IBory와 대결하기 위해 게임판을 준비해 놓고 기다리고 있었다.

만약 게임에서 진다면 영원히 훈수를 둘 수 없게 될 것이다. 과연 최적으로 행동하는 nadori를 상대할 수 있을까? IBory가 훈수를 지속할 수 있도록 훈수를 둬주자!

첫째 줄에 정점의 개수 $N$이 주어진다. $(2 \leq N \leq 100\,000)$ 

둘째 줄에 선공의 말 위치 $A$, 후공의 말 위치 $B$가 공백으로 구분되어 주어진다. $(1 \leq A, B \leq N)$ 

셋째 줄에 간선의 정보를 나타내는 수열 $L$이 공백으로 구분되어 주어진다. 이는 정점 $i$에서 정점 $L_i$로의 단방향 간선이 존재함을 의미한다. $(1 \leq L_i \leq N$; $i \ne L_i)$ 

IBory가 선공을 선택해야 한다면 first, 후공을 선택해야 한다면 second, 무엇을 선택하든 무승부라면 draw를 출력한다.

함수형 그래프는 각 정점에서 나가는 간선이 단 한 개인 방향 그래프이다.