원더랜드 추격 timer 10s memory 1024MB

앨리스는 원더랜드의 미로에 갇혀 하트 여왕과 그녀의 전령에게 쫓기고 있다! 이 미로는 \mathbf{J}개의 교차점(junction)으로 이루어져 있고, 교차점은 1번부터 \mathbf{J}번까지 번호가 매겨져 있다. 또한 교차점들은 \mathbf{C}개의 양방향 통로(corridor)로 연결되어 있다.

앨리스와 하트 여왕은 번갈아 가며 이동하고, 서로의 위치를 항상 알고 있다. (둘 중 누구든) 한 번의 이동은 현재 교차점에 그대로 있거나, 통로로 연결된 다른 교차점으로 이동하는 것이다.

하지만 여왕의 전령은 여왕이 다음에 할 이동을 미리 발표한다. 즉, 누구도 움직이기 전에 전령은 여왕의 첫 번째 이동을 발표한다. 그 다음 앨리스가 먼저 이동한다. 이후 매번 여왕이 이동할 때는 이전에 발표된 이동을 반드시 따라야 하고, 그 이동을 한 뒤에는 전령이 발표할 수 있도록 여왕의 다음 이동을 정한다. 앨리스는 이 발표를 들을 수 있으므로, 자신의 이동을 하기 전에 항상 여왕의 다음 이동을 알고 있다.

둘 중 누가 이동한 뒤에라도 앨리스와 여왕이 같은 교차점에 있다면, 앨리스는 잡힌 것이다. 그렇지 않으면 추격전이 계속된다. 총 10^9번의 이동(앨리스가 절반, 여왕이 절반)을 마칠 때까지 둘이 같은 교차점에 있지 않다면, 여왕은 포기하고 앨리스는 안전해진다.

앨리스는 탈출하기 위해 자신의 이동을 최적으로 선택한다. 만약 탈출이 불가능하다면, 잡히기까지 걸리는 총 이동 횟수를 최대화하도록 선택한다. 여왕은 앨리스를 가능한 한 적은 총 이동 횟수로 잡기 위해 최적으로 선택한다.

미로의 구조와 앨리스/여왕의 시작 위치가 주어질 때, 앨리스가 여왕에게 잡히는지 여부와, 잡힌다면 총 몇 번의 이동 후에 잡히는지를 구하라.