题目描述

小 Y 有一个随机数生成器，她想用它生成包含 $n$ 个节点的树（树是一种无环的无向连通图）。她研究了四种随机树生成方法：

1. 方法一：首先生成一个 $1$ 到 $n$ 的全排列 $p_1, p_2, \dots, p_n$。接着对于每个节点 $i$（$2 \leq i \leq n$），从 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $1$ 到 $i-1$ 中的随机整数。

2. 方法二：首先生成一个 $1$ 到 $n$ 的全排列 $p_1, p_2, \dots, p_n$。接着对于每个节点 $i$（$2 \leq i \leq n$），从 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $\lfloor \frac{i}{2} \rfloor$ 到 $i-1$ 中的随机整数。

3. 方法三：初始时有一个 $n$ 个点的图，没有边。然后等概率随机生成点对 $(u, v)$，如果 $u$ 和 $v$ 在当前图中不连通，则将边 $(u, v)$ 加入图中。重复此过程直到图连通。

4. 方法四：在所有 $n$ 个点的不同有标号树中，等概率随机选取一棵树。两棵树不同当且仅当存在一条边 $(u, v)$ 只出现在其中一棵树中。

小 Y 用这四种方法生成了很多棵 $n = 1000$ 个节点的树，但忘记了每棵树是用哪种方法生成的。你的任务是帮助她识别每棵树的生成方法。

输入格式

• 第一行包含一个正整数 $T$，表示测试数据组数。
• 接下来一个正整数 $m$，表示有 $m$ 棵树。
• 对于每棵树，输入 $n-1$ 行，每行包含两个正整数 $u, v$，表示树中的一条边。

输出格式

输出共 $m$ 行，每行一个 $1$ 到 $4$ 之间的整数，表示该树的生成方法。

数据范围与提示

• $n = 1000$
• 各测试点的 $m$ 和生成方式出现情况如下：

每个测试点中，每种可能出现的生成方式恰好出现 $1000$ 次。

评分方式

每个测试点有 $10$ 个评分参数 $a_{10}, a_9, \dots, a_1$。若你的输出中错误个数为 $x$，则得分 $2s$，其中 $s$ 是满足 $x \leq a_s$ 的最大整数。如果 $x > a_1$，得 $0$ 分。 如果输出格式有异常你将同样获得 $0$ 分，请确保你的输出中共有 $m$ 行，每行为一个 $1$ 到 $4$ 之间的正整数。 对于每个测试点的具体评分参数见附加文件中的 scores。