문제
N개의 노드와 M개의 간선(2≤N≤105, 1≤M≤2⋅105)이 있는 방향 그래프가 주어지면 Farmer John의 젖소는 다음과 같은 2인 게임을 하고 싶어합니다.
그래프의 다른 노드에 두 개의 마커를 배치합니다(마커를 일부 소 관련 항목으로 대체할 수 있음). 매 턴마다 플레이어인 "두뇌"는 나가는 가장자리를 따라 이동해야 하는 카운터를 선택합니다. 다른 플레이어인 "발굽"은 카운터를 이동할 외부 가장자리를 선택합니다. 두 개의 카운터는 항상 동일한 노드에 있을 수 없습니다. 어느 시점에서 발굽이 법적 조치를 취할 수 없으면 두뇌가 승리합니다. 게임이 무한정 계속될 수 있다면 발굽이 이깁니다.
주어진 Q 쿼리(1≤Q≤105)에는 두 개의 표시기가 있는 초기 노드가 포함됩니다. 각 쿼리에 대해 어떤 플레이어가 이겼는지 출력합니다.
입력
입력의 첫 번째 줄에는 N과 M이 포함됩니다.
다음 M 라인은 각각 두 개의 정수와 b를 포함하며, 이는 b에서 b까지의 간선을 나타냅니다.
그래프에 자체 루프 또는 다중 간선이 포함되어 있지 않습니다.
다음 줄에는 Q가 포함됩니다.
마지막 Q 라인 각각은 1≤x, y≤N 및 x≠y를 충족하는 두 개의 정수 x 및 y를 포함하며, 이는 마커가 위치한 초기 노드를 나타냅니다.
출력
길이 Q의 문자열을 출력합니다. 여기서 문자 B는 두뇌가 이기고 H는 발굽이 이긴다는 의미입니다.
예제
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4
BHHB
힌트
출처
USACO 2022 US Open Platinum
로그인해야 코드를 작성할 수 있어요.