D - Keep Perfectly Matched Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

1 から N までの番号のついた N 頂点からなる木があります． i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です． ここで N は偶数で，さらにこの木は完全マッチングを持ちます． 具体的には，各 i (1 \leq i \leq N/2) に対し，A_i=i \times 2-1,B_i=i \times 2 が保証されます．

あなたは以下の操作を N/2 回行います．

  • 葉 (次数がちょうど 1 の頂点) を 2 つ選び，木から削除する． ただしここで，削除したあとの木も完全マッチングを持つ必要がある． なお，この問題では頂点が 0 個の場合も木と呼ぶことにする．

各操作について，そのスコアを「選んだ 2 つの頂点の間の距離 (その 2 つの頂点を結ぶ単純パス上の辺の個数) 」とします．

スコアの合計を最大化するような手順を 1 つ示してください． なお，この問題の制約下で N/2 回の操作を完了する手順が常に存在することが証明できます．

制約

  • 2 \leq N \leq 250000
  • N は偶数
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq N-1)
  • A_i=i \times 2 -1,B_i=i \times 2 (1 \leq i \leq N/2)
  • 与えられるグラフは木である
  • 入力される値はすべて整数

入力

入力は標準入力から以下の形式で与えられる。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

答えを以下の形式で出力せよ．

X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}

ここで，X_i,Y_i は i 回目の操作で選ぶ 2 つの頂点である． 解が複数存在する場合，どれを出力しても構わない．

入力例 1

4
1 2
3 4
2 3

出力例 1

4 1
2 3

出力例の手順は以下の通りです．

  • 1 回目の操作: 頂点 4,1 を消す．残る木は頂点 2,3 からなり，完全マッチングを持つ．操作のスコアは 3 である．
  • 2 回目の操作: 頂点 2,3 を消す．残る木は 0 頂点からなり，完全マッチングを持つ．操作のスコアは 1 である．
  • スコアの合計は 3+1=4 になる．

スコアの合計を 4 より大きくすることはできないので，この入力例はこの出力で正解できます．

入力例 2

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

出力例 2

4 8
7 6
5 3
2 1

入力例 3

14
1 2
3 4
5 6
7 8
9 10
11 12
13 14
2 8
4 11
5 12
7 13
11 14
9 13

出力例 3

1 6
5 2
8 12
3 7
10 4
11 9
13 14

入力例 4

20
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
8 10
16 18
16 19
5 9
10 17
2 13
7 14
3 7
3 12

出力例 4

6 1
2 15
20 13
14 19
16 4
11 18
17 12
3 5
9 7
8 10

Score : 800 points

Problem Statement

There is a tree with N vertices numbered from 1 to N. The i-th edge connects vertices A_i and B_i. Here, N is even, and furthermore, this tree has a perfect matching. Specifically, for each i (1 \leq i \leq N/2), it is guaranteed that A_i=i \times 2-1 and B_i=i \times 2.

You will perform the following operation N/2 times:

  • Choose two leaves (vertices with degree exactly 1) and remove them from the tree. Here, the tree after removal must still have a perfect matching. In this problem, we consider a graph with zero vertices to be a tree as well.

For each operation, its score is defined as the distance between the two chosen vertices (the number of edges on the simple path connecting the two vertices).

Show one procedure that maximizes the total score. It can be proved that there always exists a procedure to complete N/2 operations under the constraints of this problem.

Constraints

  • 2 \leq N \leq 250000
  • N is even.
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq N-1)
  • A_i=i \times 2 -1, B_i=i \times 2 (1 \leq i \leq N/2)
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Print a solution in the following format:

X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}

Here, X_i and Y_i are the two vertices chosen in the i-th operation. If there are multiple solutions, you may print any of them.

Sample Input 1

4
1 2
3 4
2 3

Sample Output 1

4 1
2 3

The procedure in the sample output is as follows:

  • 1st operation: Remove vertices 4 and 1. The remaining tree has vertices 2 and 3, and a perfect matching. The score of this operation is 3.
  • 2nd operation: Remove vertices 2 and 3. The remaining tree has zero vertices and a perfect matching. The score of this operation is 1.
  • The total score is 3 + 1 = 4.

It is impossible to make the total score greater than 4, so this output solves this sample input.

Sample Input 2

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

Sample Output 2

4 8
7 6
5 3
2 1

Sample Input 3

14
1 2
3 4
5 6
7 8
9 10
11 12
13 14
2 8
4 11
5 12
7 13
11 14
9 13

Sample Output 3

1 6
5 2
8 12
3 7
10 4
11 9
13 14

Sample Input 4

20
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
8 10
16 18
16 19
5 9
10 17
2 13
7 14
3 7
3 12

Sample Output 4

6 1
2 15
20 13
14 19
16 4
11 18
17 12
3 5
9 7
8 10