CF1879E.Interactive Game with Coloring

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

You are given a tree on $n$ vertices; vertex $1$ is the root of the tree. For every $i \in [2, n]$, the parent of the $i$-th vertex is $p_i$, and $p_i \lt i$.

You have to color all edges of the tree using the minimum possible number of colors such that you can win the game on that tree (every edge should be painted into exactly one color).

The game we're going to play will be conducted as follows. After you paint the edges and print their colors, the jury will place a chip into one of the vertices of the tree (except for the root). Your goal is to move this chip to the root in exactly $d$ moves, where $d$ is the distance from the root to that vertex (the distance is equal to the number of edges on the path). If the chip reaches the root in $d$ moves, you win. Otherwise, you lose.

The jury won't tell you where the chip is located. You won't even know the value of $d$ in advance. However, at the start of each move, you will be told how many edges of each color are incident to the current vertex (this includes both the edge leading up the tree and the edges leading away from the root). You have to choose one of these colors, and the chip will be moved along the edge of the chosen color (if there are multiple edges with that color incident to the current vertex, the jury gets to choose one of them). After the chip is moved, you will be told the same information about the current vertex again, and the game continues, until you either reach the root, or you make $d$ moves without reaching the root.

The interactor for this problem is adaptive. It means that both the starting vertex and the current vertex are not fixed and may change "on the run" depending on the output of your program. However, the state of the game will always be consistent with the information you are given: there will always be at least one starting vertex and at least one path of your chip from that vertex consistent with both the information about the colors you receive and the colors you've chosen during the moves.

这是一个交互式问题。在与评测程序通信时，请务必刷新你的输出。你可以使用 C++ 中的 fflush(stdout)、Java 中的 System.out.flush()、Python 中的 stdout.flush() 或 Pascal 中的 flush(output) 来刷新输出。若使用其他编程语言，请查阅其文档。你也可以参考交互式问题指南：https://codeforces.com/blog/entry/45307。

你被给定一棵含 $n$ 个顶点的树；其中顶点 $1$ 是树的根。对每个 $i \in [2, n]$，第 $i$ 个顶点的父节点为 $p_i$，且满足 $p_i < i$。

你需要用尽可能少的颜色对树的所有边进行染色，使得你在该树上能赢得接下来的游戏（每条边必须且仅被染成一种颜色）。

我们将进行如下游戏：在你完成边的染色并输出各边颜色后，出题方会将一个棋子放置在树的某个顶点（根节点除外）。你的目标是在恰好 $d$ 步内将该棋子移动至根节点，其中 $d$ 是该顶点到根节点的距离（即路径上的边数）。若棋子恰在 $d$ 步后抵达根节点，则你获胜；否则，你失败。

出题方不会告诉你棋子初始位于哪个顶点，你甚至无法预先得知 $d$ 的值。然而，在每一步开始时，你会被告知当前顶点处每种颜色的关联边数（包括指向父节点的边和指向子节点的边）。你必须从中选择一种颜色，随后棋子将沿该颜色的一条关联边移动（若当前顶点有多个同色关联边，则由出题方从中任选一条）。棋子移动后，你将再次获知新顶点处每种颜色的关联边数，游戏继续进行，直至棋子抵达根节点，或你在 $d$ 步内未能抵达根节点。

本题的交互器是自适应的。这意味着棋子的起始顶点以及每一步的当前顶点均非固定，而可能根据你的程序输出“动态变化”。但游戏状态始终与你所获得的信息保持一致：总存在至少一个合法的起始顶点，以及至少一条从该顶点出发、符合你每步所获颜色信息及你所选颜色的棋子移动路径。

The first line contains one integer $n$ ($3 \le n \le 100$) — the number of vertices in the tree.

The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \lt i$), where $p_i$ is the parent of the $i$-th vertex in the tree.

第一行包含一个整数 $n$（$3 \le n \le 100$）—— 树中顶点的数量。

第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i \lt i$），其中 $p_i$ 表示树中第 $i$ 个顶点的父节点。

In the first example, every vertex from $2$ to $n$ is connected to the root. So, we can paint all edges into the same color $1$, and when the game starts, there will be only one edge incident to the current vertex (and it will lead to the root).

In the second example, the tree is a path of $4$ vertices. We have to paint its edges into different colors, because it can be shown that we don't have a winning strategy with just two colors.

在第一个例子中，从 $2$ 到 $n$ 的每个顶点均与根节点相连。因此，我们可以将所有边涂成同一种颜色 $1$；当游戏开始时，当前顶点仅关联一条边（且该边指向根节点）。

在第二个例子中，该树是一条包含 $4$ 个顶点的路径。我们必须将它的各条边涂成互不相同的颜色，因为可以证明：仅使用两种颜色时，我们并不存在必胜策略。