这是一个交互式问题。

Fred 和 Fiona 在无聊的课上玩井字棋玩腻了，于是他们发明了一个新游戏。 游戏的棋盘是一个连通的无环无向图，也就是一棵树。玩家轮流进行操作，Fred 先手。玩家使用四种颜色的铅笔进行游戏：红色、绿色、蓝色和黄色，我们将这些颜色分别记为整数 1 到 4。

初始时，树的所有顶点均未着色。每一轮，当前玩家选择一个未着色的顶点，并将其涂上四种颜色中的一种，要求与该顶点相邻的任何顶点颜色不能相同。

如果当前玩家因为所有顶点都已着色，或者没有顶点可以合法着色而无法操作，游戏结束，胜负判定如下：如果所有顶点都已着色，则 Fred 获胜；如果仍有未着色的顶点，则 Fiona 获胜。

朋友们玩了很多局游戏，Fiona 注意到 Fred 总是获胜。经过思考，她意识到 Fred 找到了一种必胜策略。你能做到吗？

交互

你的程序将通过标准输入和标准输出与评测程序进行交互。

首先，你的程序必须读取树的描述。输入包含 $n$（顶点数，$2 \le n \le 1000$），随后是 $n-1$ 对顶点 $u_i, v_i$，表示树的边（顶点编号从 1 到 $n$）。

接着交互按如下方式进行：你的程序首先输出一个未着色的顶点编号 $u$ 和你希望涂上的颜色 $c$ 到标准输出。然后，必须从标准输入读取对手的移动（格式相同），接着进行你的移动，以此类推。

当游戏结束且你的程序获胜时（通过涂上最后一个顶点，或者迫使评测程序涂上最后一个顶点），你的程序将从标准输入读取到 “$-1 -1$” 而不是对手的移动。读取后，你的程序必须终止。尽管你可能提前推断出自己已经获胜，或者意识到你的移动是最后一步，但你必须在读取到 “$-1 -1$” 后才退出。

样例

样例输入 1

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

样例输出 1

1 1
7 2
3 4
2 3

说明

样例输入格式旨在展示输出如何响应对应的输入。在实际交互中不会有空行。

在给出的样例中，评测程序进行了最后一步移动（可能是 “5 1”、“5 2” 或 “5 4”），但没有将其报告给你的程序，因为在那之后游戏已经结束，且你的程序获胜。