Arezou와 Borzou는 쌍둥이다.

생일에 장난감 기차 세트를 받아서 그 세트로 n개의 역과 m개의 단방향 철로가 있는 철도시스템을 만들었다.

역들은 0번 부터 n-1번까지 번호가 붙어 있다.

각 철로는 한 역에서 출발해, 자기 자신이나 다른 역에 도착한다.

각 역에는 그 역에서 출발하는 철로가 최소 하나 있다.

어떤 역들은 충전역이다.

충전역에 기차가 도착하면 기차의 배터리가 완전히 충전된다.

완전히 충전된 기차는 n개의 철로를 지날 수 있다.

즉, 완전히 충전된 상태의 기차는 (더 이상의 충전이 없다면) n개의 철로를 지나고 n+1번째의 철로에 들어가는 시점에 배터리가 방전되어 멈춘다.

각 역에는 그 역을 출발하는 어떤 철로로든 기차를 보낼 수 있는 스위치가 있다.

기차가 어떤 역에서 출발할 때는 그 역의 스위치가 지정한 방향으로만 떠난다.

쌍둥이는 철로시스템을 가지고 게임을 하려고 한다.

쌍둥이는 모든 역의 소유권을 정했다.

즉, 하나의 역은 Arezou와 Borzou 두 명 중 정확히 한 명이 소유한다.

기차는 한 대를 사용한다.

게임의 시작에 기차는 어떤 역 s에 있고 완전히 충전되어 있다.

게임의 시작에 s의 소유자가 s의 스위치를 세팅하여 기차가 특정한 철로로 출발하도록 한다. 그 다음, 기차의 전원을 켜고 기차가 움직인다.

기차가 어떤 역에 최초로 도착하면, 그 역의 소유자가 역의 스위치를 세팅한다.

역의 스위치를 한번 세팅하면 게임이 진행되는 동안 바뀌지 않는다.

즉, 기차가 동일한 역에 다시 도착한다면 지난번에 출발했던 철로로 다시 출발하게 된다.

역의 개수가 유한하므로, 기차는 어떤 사이클에 들어갈 수밖에 없다.

사이클은 서로 다른 역 c₀, ..., c_k-1의 순서인데, 모든 0 ≤ i < k-1에 대해 c_i에서 출발해서 c_i+1에 철로를 통해 도착하며, c_k-1에서 출발해서 c₀에 철로를 통해 도착한다.

어떤 역 c₀에서 기차가 출발해서 자기 자신 c₀에 철로를 통해 도착한다면, 사이클이 단 하나의 역으로 (즉, k = 1) 구성되는 것도 가능하다.

기차가 무한히 오랫동안 달릴 수 있으면 Arezou가 이기고, 기차가 멈추는 경우 Borzou가 이긴다.

다르게 설명하면, 사이클 c₀, ... c_k-1에 충전역이 하나라도 있다면 기차가 충전을 반복하며 무한히 달릴 수 있어서 Arezou가 이긴다.

그렇지 않다면 (어쩌면 사이클을 몇 바퀴 돈 후에) 전력이 떨어져서 기차는 멈출 것이고, Borzou가 이긴다.

당신은 철도시스템의 구성을 입력으로 받는다. Arezou와 Borzou는 n번의 게임을 할 것이다.

이들 중 s번째 (0 ≤ s ≤ n-1) 게임에서, 게임의 시작에 기차는 역 s에 있다.

당신은 각 게임에서 (Borzou가 어떤 일을 하더라도) Arezou가 항상 이길 수 있는 방법이 있는지 알아내는 프로그램을 작성해야 한다.

Toy Train timer 2초 memory 256MB

Toy Train 2초 256MB