N개의 노드와 M개의 간선(2≤N≤10⁵, 1≤M≤2⋅10⁵)이 있는 방향 그래프가 주어지면 Farmer John의 젖소는 다음과 같은 2인 게임을 하고 싶어합니다.

그래프의 다른 노드에 두 개의 마커를 배치합니다(마커를 일부 소 관련 항목으로 대체할 수 있음). 매 턴마다 플레이어인 "두뇌"는 나가는 가장자리를 따라 이동해야 하는 카운터를 선택합니다. 다른 플레이어인 "발굽"은 카운터를 이동할 외부 가장자리를 선택합니다. 두 개의 카운터는 항상 동일한 노드에 있을 수 없습니다. 어느 시점에서 발굽이 법적 조치를 취할 수 없으면 두뇌가 승리합니다. 게임이 무한정 계속될 수 있다면 발굽이 이깁니다.

주어진 Q 쿼리(1≤Q≤10⁵)에는 두 개의 표시기가 있는 초기 노드가 포함됩니다. 각 쿼리에 대해 어떤 플레이어가 이겼는지 출력합니다.

#5323 upload 28 done 5 how_to_reg 5

발굽과 두뇌 timer 4s memory 256MB

#5323

발굽과 두뇌 4s 256MB