이 문제는 다중 패스 인터랙티브 문제입니다. 매 출력 후에는 반드시 출력 버퍼를 비워야 합니다. 출력 버퍼를 비우려면 다음을 사용할 수 있습니다.

• C/C++: fflush(stdout) 또는 cout.flush()
• Java 및 Kotlin: System.out.flush()
• Python: sys.stdout.flush()

고전적인 온라인 매칭 게임에서 그래프의 간선은 하나씩 공개됩니다. 간선이 주어질 때마다, 당신은 즉시 그리고 돌이킬 수 없게 해당 간선을 매칭에 포함할지 여부를 결정해야 합니다. 당신의 목표는 선택된 두 간선이 정점을 공유하지 않도록 하면서 선택된 간선의 총 개수를 최대화하는 것입니다.

당신은 명성을 갈망하는 야심 찬 컴퓨터 과학자입니다. 잘 알려져 있듯이, 이분 그래프와 같은 가장 단순한 그래프 클래스에 대해서조차 온라인 환경에서 최대 매칭을 찾는 것은 높은 확률로 불가능함이 증명되어 있습니다. 그러나 다른 사람들이 근본적인 장벽을 볼 때, 당신은 영광을 위한 기회를 봅니다. 오늘, 당신은 트리(tree)에 대한 오랜 난제를 해결했다고 주장하며 당신의 획기적인 알고리즘을 세상에 공개할 준비가 되었습니다.

단 한 가지 문제가 있습니다. 어제 당신은 증명에서 버그를 발견했고, 아직 그것을 어떻게 고쳐야 할지 모릅니다. 주목받는 것을 포기하고 싶지 않았던 당신은 시연을 마술 쇼로 바꾸기로 결정했습니다. 게임이 시작되기 전에 숨어 있는 조수가 $n$개의 정점을 가진 전체 트리에 대한 작은 힌트를 전달할 것입니다.

당신의 원래 계획은 간단했습니다. 조수가 각 간선 쿼리에 대한 답을 직접 보내게 하는 것입니다. 이를 위해 당신은 길이가 $(n - 1)$인 단일 이진 문자열을 수신할 수 있는 비밀 이어폰을 설치했습니다. 하지만 관객들은 당신의 "돌파구"에 회의적입니다. 사전에 조작된 속임수를 방지하기 위해, 그들은 간선들이 당신이나 당신의 조수가 예측하거나 제어할 수 없는 균등 무작위 순서로 제시되어야 한다고 요구합니다.

무대는 준비되었고, 조명은 당신을 비추고 있습니다. 이제 채널을 돌리지 말고 당신의 주장을 증명하십시오.

인터랙션 프로토콜

당신의 솔루션은 각 테스트 케이스마다 두 번 실행됩니다. prepare 라운드에서 당신의 솔루션은 조수 역할을 수행합니다. play 라운드에서 당신의 솔루션은 마술사인 당신의 역할을 수행합니다. 어느 라운드에서든 당신의 솔루션은 인터랙티브 절차로 평가됩니다.

Prepare 라운드

입력의 첫 번째 줄에는 prepare라는 단어가 포함됩니다. 두 번째 줄에는 정점의 개수인 정수 $n$ ($2 \le n \le 500$)이 주어집니다. 이어지는 $(n - 1)$개의 줄에는 트리에서 $u$와 $v$ 사이의 무방향 간선을 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n, u < v$)가 주어집니다.

당신은 정확히 길이가 $(n - 1)$이고 0과 1로만 구성된 이진 문자열 $s$를 한 줄 출력해야 합니다. 이 문자열은 두 번째 play 라운드로 전달됩니다. 출력 형식이 올바르지 않으면 Wrong Answer 판정을 받게 됩니다.

Play 라운드

당신의 솔루션은 play 라운드를 위해 재시작됩니다.

첫 번째 줄에는 play라는 단어가 포함됩니다. 두 번째 줄에는 정수 $n$이 포함됩니다. 세 번째 줄에는 prepare 라운드에서 출력했던 이진 문자열 $s$가 그대로 포함됩니다.

그 후, $(n - 1)$번의 턴으로 게임이 시작됩니다. 각 턴마다 두 정수 $u$와 $v$ ($1 \le u, v \le n, u < v$)가 포함된 줄이 제공됩니다. 응답으로 take 또는 ignore 중 하나를 한 줄 출력해야 합니다. 첫 번째 라운드의 모든 간선은 정확히 한 번씩 제공되며, 간선의 순서는 $(n - 1)!$개의 가능한 순열 중에서 균등 무작위로 선택됩니다.

출력 형식이 올바르지 않으면 인터랙터로부터 더 이상의 정보 없이 게임이 즉시 종료됩니다.

정답 판정

$M$을 당신의 솔루션이 선택한 간선들의 집합이라고 합시다. 어떤 정점도 선택된 간선 두 개 이상과 연결되어 있지 않고, $|M| = |M^*|$ ($M^*$은 그래프의 최대 매칭)이면 허용 가능한 것으로 간주합니다.

샘플 테스트를 제외하고 정확히 50개의 테스트 케이스가 있습니다. 이 문제를 통과하려면 샘플 테스트를 포함한 모든 테스트 케이스에서 솔루션이 올바르게 작동해야 합니다.

모든 셔플은 솔루션의 출력을 받기 전에 고정되는 것이 보장됩니다. 각 테스트에 대한 무작위성은 의사 난수 생성기의 시드를 고정함으로써 결정됩니다.

솔루션 개발 및 테스트를 돕기 위한 테스트 도구가 제공됩니다.

예제

예제 1 (Pass 1)

prepare
3
1 2
1 3

00

예제 1 (Pass 2)

play
3
00
1 3

take

1 2

ignore

참고

예제 1에 대한 설명: $|M^*| = 1$이므로, 어떤 간선을 선택해도 허용되며 힌트는 임의적일 수 있습니다.

Magically Marked Matching Master