장난감 기차

Arezou와 그녀의 남동생 Borzou는 쌍둥이다. 두 사람은 생일 선물로 멋진 장난감 기차 세트를 받았고, 그것으로 $n$개의 역과 $m$개의 단방향 선로를 가진 철도 시스템을 만들었다. 역은 $0$부터 $n-1$까지 번호가 붙어 있다. 각 선로는 어떤 역에서 시작해 같거나 다른 역에서 끝난다. 모든 역에서 적어도 하나의 선로가 시작한다.

일부 역은 충전소이다. 기차가 충전소에 도착할 때마다 기차는 완전히 충전된다. 완전히 충전된 기차는 $n$개의 연속한 선로를 지날 만큼의 에너지를 가지고 있다. 즉, 마지막으로 충전된 뒤 $(n+1)$번째 선로에 진입하는 순간 기차는 에너지를 모두 소모한다.

각 역에는 그 역에서 시작하는 선로 중 아무 곳이나 가리킬 수 있는 전환기가 있다. 기차가 어떤 역에 있을 때, 기차는 그 역의 전환기가 가리키는 선로를 이용해 역을 떠난다.

쌍둥이는 기차를 가지고 게임을 하려고 한다. 두 사람은 이미 모든 역을 서로 나누어 가졌다. 각 역은 Arezou 또는 Borzou 중 한 사람의 소유이다. 기차는 한 대뿐이다. 게임이 시작될 때 기차는 역 $s$에 있고 완전히 충전되어 있다. 게임을 시작하려면 역 $s$의 주인이 역 $s$의 전환기를 역 $s$에서 시작하는 선로 중 하나로 가리킨다. 그런 다음 기차를 켜면 기차는 선로를 따라 움직이기 시작한다.

기차가 처음 진입하는 역에 도착할 때마다 그 역의 주인이 그 역의 전환기를 설정한다. 한 번 설정된 전환기는 게임이 끝날 때까지 같은 위치에 있다. 따라서 기차가 이전에 방문한 역에 다시 들어가면, 그 역을 이전과 같은 선로로 떠난다.

역의 수가 유한하므로 기차는 언젠가 사이클을 따라 움직이기 시작한다. 사이클은 서로 다른 역의 수열 $c[0], c[1], \cdots, c[k-1]$로, 기차가 역 $c[i]$($0 \leq i < k-1$)를 떠날 때 역 $c[i+1]$로 가는 선로를 이용하고, 역 $c[k-1]$을 떠날 때 역 $c[0]$으로 가는 선로를 이용하는 것이다. 기차가 역 $c[0]$에서 $c[0]$으로 돌아오는 선로를 이용하면 사이클이 역 하나로 이루어질 수도 있다($k=1$).

기차가 무한히 계속 움직이면 Arezou가 이기고, 기차의 에너지가 바닥나면 Borzou가 이긴다. 다시 말해, $c[0], c[1], \cdots, c[k-1]$ 중에 충전소가 적어도 하나 있으면 기차는 충전하며 무한히 사이클을 돌 수 있고 Arezou가 이긴다. 그렇지 않으면 기차는 (사이클을 여러 번 돌고 난 뒤일 수도 있지만) 에너지가 바닥나고 Borzou가 이긴다.

철도 시스템의 정보가 주어진다. Arezou와 Borzou는 $n$번의 게임을 한다. $s$번째 게임($0 \leq s \leq n-1$)에서 기차는 처음에 역 $s$에 있다. 각 게임마다 Borzou가 어떻게 두든 Arezou가 승리를 보장할 전략이 있는지 판별하시오.

• $1 \leq n \leq 5000$.
• $n \leq m \leq 20\,000$.
• 충전소가 적어도 하나 있다.
• 모든 역에서 적어도 하나의 선로가 시작한다.
• 같은 역에서 시작하고 끝나는 선로가 있을 수 있다. 즉, $u[i] = v[i]$일 수 있다.
• 각 선로는 서로 다르다. 다시 말해, $u[i]=u[j]$이고 $v[i]=v[j]$인 두 인덱스 $i$와 $j$($0 \leq i < j \leq m-1$)는 존재하지 않는다.
• 모든 $0 \leq i \leq m-1$에 대해 $0 \leq u[i], v[i] \leq n-1$.