33OJ
登录 注册

#P17501. [ICPC 2026 Wuhan I] Nailoong vs. Bombloong 2

    ID: 20229 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>交互题Special JudgeICPC2026通信题省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Nailoong vs. Bombloong 2

Problem Description

This is a communication problem. In this problem, your program will be run twice. Between the two runs, all variables stored in memory will be lost, but the information obtained in the first run may be crucial for correctly solving the problem in the second run.

There are two characters in this problem: “Nailoong” and “Bombloong”.

Nailoong has the complete structural information of a tree with nn nodes, while Bombloong only knows the number of nodes nn. Since Bombloong has been imprisoned by the evil Little Leopard, Nailoong can only help Bombloong reconstruct a tree that is isomorphic to the original tree through a special one-way communication method.

The rules of communication are as follows:

  • Initially, all nodes in the tree are white.
  • Nailoong can perform m≤n−3m \le n-3 operations (the value of mm is determined by Nailoong).
  • In the ii-th operation, Nailoong needs to choose a node xix_i on the tree and flip its color (white to black, black to white).
  • After each flip, let aia_i be the number of edges in the current tree whose two endpoints have different colors.
  • After mm operations, Nailoong obtains a sequence a1,a2,⋯ ,ama_1,a_2,\cdots,a_m of length mm.

Nailoong cannot directly send node indices to Bombloong; she can only send the total number of operations mm and the sequence aa to Bombloong. After receiving nn, mm, and the sequence aa, Bombloong needs to construct and output a tree that is isomorphic to Nailoong's tree.

Communication Protocol

In each test case, the contestant's program will be run twice. A testing tool is provided in the handout files for local debugging.

First Run

In the first run, you will play the role of “Nailoong”.

Input

The first line of input contains an integer 11, which allows your program to identify that this is the first run.

The second line contains an integer nn (4≤n≤3×1054 \le n \le 3\times10^5), representing the number of nodes in the tree.

The next n−1n-1 lines each contain two integers u,vu,v (1≤u,v≤n1 \le u,v \le n), representing an edge in the tree.

Output

The first line of output should contain an integer mm (0≤m≤n−30 \le m \le n-3), representing the number of operations.

The second line contains mm integers x1,x2,⋯ ,xmx_1,x_2,\cdots,x_m (1≤xi≤n1 \le x_i \le n), representing the indices of the nodes flipped by Nailoong in each operation in sequence.

Second Run

In the second run, you will play the role of “Bombloong”.

Input

The first line of input contains an integer 22, which allows your program to identify that this is the second run.

The second line contains two integers n,mn,m (4≤n≤3×1054 \le n \le 3\times10^5, 0≤m≤n−30 \le m \le n-3), representing the number of nodes and the number of operations performed by Nailoong, respectively.

If m>0m>0, the third line contains mm integers a1,a2,⋯ ,ama_1,a_2,\cdots,a_m (0≤ai≤n0 \le a_i \le n), representing the sequence generated by the judge based on Nailoong's operations; if m=0m=0, the third line does not exist.

Output

Output n−1n-1 lines, each containing two integers u,vu,v, representing an edge of the tree you reconstructed (1≤u,v≤n1 \le u,v \le n). You must ensure that the output tree is isomorphic to the tree provided in the input of the first run.

First Run

standard input

1
4
1 2
2 3
3 4

standard output

1
2

Second Run

standard input

2
4 1
2

standard output

1 3
3 2
2 4

Hint

The two samples demonstrate the two runs within the same test case.

Nailoong flipped node 22. At this point, the number of edges with different colored endpoints is 22, so a1=2a_1=2.

Bombloong received the sequence a=[2]a=[2]. Since Bombloong and Nailoong share a deep connection, she immediately guessed the structure of the tree. Although the tree obtained by Bombloong differs from the tree Nailoong held in terms of node indexing, they are isomorphic, so it is still considered correct.