이 문제는 인터랙티브 문제입니다. 매번 출력 후 표준 출력 버퍼를 비워야 합니다. 각 프로그래밍 언어별 방법은 다음과 같습니다.

• C/C++의 경우, fflush(stdout) 또는 cout.flush()를 사용하십시오.
• Java의 경우, System.out.flush()를 사용하십시오.
• Python의 경우, sys.stdout.flush()를 사용하십시오.

전력망 복구가 완료되고, 전광판이 성공적으로 가동되었습니다. 밤이 깊어짐에 따라 공중에 떠 있는 전광판이 화려하게 빛납니다. 모든 준비가 끝나고, T와 S는 야간 활동의 막을 올리며 여러분을 초대하여, 두 사람의 협동심을 시험하는 빛과 그림자의 게임 "유광해밀(流光解密)"에 참여하게 했습니다.

광장 중앙의 빛줄기가 서로 얽히며 천천히 하나의 전광수(全光树)로 모여듭니다. 전광수는 여러 개의 떠 있는 광단(光团) 노드와 그들을 연결하는 유광 회선으로 구성되어 있으며, 순수한 트리 구조를 나타냅니다. 게임이 시작될 때, 모든 회선은 켜지지 않아 도전자들은 켜진 회선을 관찰할 수 없습니다. 시스템을 운영하는 Karuha는 먼저 제어대 앞에 있는 도전자에게 하나의 신비한 숫자 $s$를 보여줍니다. 그 후, 각 유광 회선이 하나씩 켜지며, 해당 도전자는 회선이 나타나는 순간마다 그 흐름의 방향을 결정해야 합니다. 무대 반대편에 서 있는 파트너는 최종적으로 형성된 방향성 트리 구조만을 보고, 이 신비한 숫자 $s$를 정확히 추론해야 합니다.

축제 참가자인 Neri와 Noir는 협력하여 이 도전을 완수하기로 했습니다.

문제 설명

이 도전에서 Neri는 제어대 앞에 서게 됩니다. 시스템의 Karuha는 먼저 그녀에게 두 개의 정수 $n, s$ ($1 \le s \le 2^{n-1}$)를 주며, 각각 전광수에 포함된 광단의 개수와 신비한 숫자를 나타냅니다.

그 후, Karuha는 차례대로 $n - 1$개의 유광 회선을 켭니다. Neri는 각 회선이 켜질 때마다 즉시 그 흐름의 방향을 지정해야 합니다.

주 무대 반대편에 서 있는 Noir는 빛으로 가득 찬 전광수의 최종 형태를 관찰하게 됩니다. 그녀는 이 회선들의 흐름 방향을 바탕으로 Karuha가 Neri에게 전달한 신비한 숫자 $s$를 추론해야 합니다.

이 빛과 그림자의 게임에서 승리하기 위해, Neri와 Noir는 이 두 사람의 호흡을 시험하는 게임을 성공적으로 통과할 수 있도록 사전에 전략을 세워야 합니다.

구현 세부사항

당신의 프로그램은 독립적으로 두 번 실행됩니다. 첫 번째 실행에서는 Neri 역할을 맡아 각 회선의 흐름 방향을 결정하고, 두 번째 실행에서는 Noir 역할을 맡아 전광수의 최종 형태를 바탕으로 신비한 숫자를 추론합니다. 인터랙터가 Karuha 역할을 맡아 당신의 프로그램에 정보를 전달합니다.

첫 번째 실행에서, 당신의 프로그램은 먼저 전광수에 포함된 광단의 개수 $n$과 신비한 숫자 $s$를 받은 다음, 차례대로 $n - 1$개의 켜지는 유광 회선을 받습니다. 당신의 프로그램은 즉시 인터랙터에게 지정한 흐름 방향을 출력해야 하며, 이를 통해 두 번째 실행으로 정보를 전달합니다.

두 번째 실행에서, 당신의 프로그램은 인터랙터로부터 첫 번째 실행에서 전달된 정보, 즉 전광상의 유광 회선들의 흐름 방향을 받고, 이 정보를 바탕으로 Karuha가 Neri에게 전달한 신비한 숫자 $s$를 추론해야 합니다.

입력 및 출력 형식

각 테스트 케이스에는 여러 개의 테스트 데이터가 포함되어 있습니다. 입력의 첫 번째 줄에는 두 개의 정수 $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$)이 주어지며, 각각 테스트 케이스의 개수와 단계 번호를 나타냅니다. 각 테스트 데이터에 대하여:

• $r = 1$인 경우:

  • 첫 번째 줄에 두 개의 정수 $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$)가 주어지며, 각각 전광수에 포함된 광단의 개수와 신비한 숫자를 나타냅니다.
  • 그다음 $n - 1$개의 유광 회선이 차례대로 켜집니다. 회선이 하나 켜질 때마다 두 개의 정수 $u, v$ ($1 \le u < v \le n$)가 입력되며, 이는 유광 회선으로 연결된 두 광단의 번호를 나타냅니다. 당신은 즉시 $u$에서 $v$로 흐르는 방향을 나타내는 u v 또는 $v$에서 $u$로 흐르는 방향을 나타내는 v u를 출력해야 합니다.
  • 주의: 각 유광 회선에 대해, 반드시 해당 유광 회선의 흐름 방향을 출력하고 표준 출력 버퍼를 비운 후에야 다음 켜지는 유광 회선을 입력받을 수 있습니다.

• $r = 2$인 경우:

  • 첫 번째 줄에 하나의 정수 $n$ ($3 \le n \le 30$)이 주어지며, 전광수에 포함된 광단의 개수를 나타냅니다.
  • 그다음 $n - 1$개의 줄에 걸쳐, 각 줄마다 두 개의 정수 $u, v$ ($1 \le u, v \le n$)가 입력되며, 이는 광단 $u$에서 광단 $v$로 흐르는 유광 회선을 나타냅니다.
  • 당신은 즉시 추론한 신비한 숫자 $s$를 한 줄에 출력해야 합니다.
  • 주의:
    • 단일 테스트 케이스 내에서 테스트 데이터 입력의 순서는 첫 번째 실행과 다를 수 있습니다.
    • 동일한 테스트 데이터에 대해, 유광 회선이 입력되는 순서는 두 번의 실행에서 다를 수 있지만, 광단의 번호는 변하지 않습니다.
    • 각 테스트 데이터에 대해, 반드시 추론한 신비한 숫자 $s$를 출력하고 표준 출력 버퍼를 비운 후에야 다음 테스트 데이터를 입력받을 수 있습니다.

Figure 1. 첫 번째 테스트 데이터

Figure 2. 두 번째 테스트 데이터

예제

입력 1

2 1
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
8 9
9 21
2 7
1 6
3 5
2 4
3 4
1 2
6 7
8 9

출력 1

6 1
3 5
4 2
3 4
1 2
7 6
1 2
1 4
3 4
3 5
8 3
5 6
6 7
9 8

입력 2

2 2
9
5 9
1 2
5 6
6 7
1 4
3 5
8 3
3 4
9
1 2
4 2
6 1
3 5
3 4
7 6
2 7
8 9

출력 2

59
21

참고

제공되는 파이썬 스크립트 treedir_testing_tool.py를 사용하여 로컬에서 프로그램의 정확성을 검증하고 상세한 인터랙션 과정을 확인할 수 있습니다. 테스트 시, 해당 스크립트를 컴파일된 실행 파일과 같은 디렉토리에 두고 터미널에서 다음 명령어를 실행하십시오:

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

• -q, --quiet: 선택적 매개변수로, 이 매개변수를 사용하면 테스트 스크립트가 상세한 인터랙션 과정을 출력하지 않습니다.
• data_file: 테스트 스크립트에 제공할 입력 파일 경로입니다. 파일 형식은 다음과 같습니다:
  • 첫 번째 줄에 두 개의 음이 아닌 정수 $T, seed$가 포함되며, 각각 테스트 데이터의 개수와 테스트 순서 및 트리 내 간선 순서를 섞기 위한 랜덤 시드를 나타냅니다. $seed = 0$으로 지정하면 섞지 않습니다.
  • 각 테스트 데이터의 형식은 앞서 설명한 "첫 번째 실행"의 입력 형식과 완전히 동일합니다.
• program: 컴파일된 실행 파일의 경로입니다.
• arguments: 해당 실행 파일에 전달할 추가 명령줄 매개변수입니다.

주의: 1. 테스트 스크립트와 실제 평가 시의 인터랙터 구현은 완전히 동일하지 않으므로, 로컬 테스트 결과는 최종적인 것이 아니며 디버깅 단계에서만 참고하십시오. 2. 테스트 스크립트는 data_file 내의 데이터에 대해 기본적인 형식 검사만 수행하며, 문제의 제약 조건을 올바르게 만족하는지(예: $s$가 $1 \le s \le 2^{n-1}$을 만족하는지, 유광 회선이 올바르게 하나의 트리를 구성하는지 등)는 검사하지 않습니다. 3. 테스트 스크립트는 프로그램의 시간 및 공간 소모를 모니터링하지 않으므로, 문제의 시간 및 공간 제한을 준수하는지 테스트하는 데 사용할 수 없습니다.