题目描述

小 Y 最近有了一个随机数生成器 (random number generator)。小 Y 想用这个随机数生成器生成 $n$ 个节点的树。树为一种没有环的无向连通图。

经过小 Y 的研究，她发现了 $4$ 种随机树生成方法。

第一种方法为首先生成一个 $1$ 到 $n$ 的全排列 $p_1,p_2,…,p_n$。接着对于所有的节点 $i (2 \leq i \leq n)$，由 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $1$ 到 $i-1$ 中的随机整数。

第二种方法为首先生成一个 $1$ 到 $n$ 的全排列 $p_1,p_2,…,p_n$。接着对于所有的节点 $i (2 \leq i \leq n)$，由 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $\lfloor \frac {i}{2} \rfloor$ 到 $i-1$ 中的随机整数。

第三种方法为首先有一个 $n$ 个点的图，里面没有边。接着等概率地随机生成点对 $u,v$ ，如果当前图中 $u,v$ 不连通，那么将边 $(u,v)$ 加入到图中。重复这个过程，直到这个图连通为止。

第四种方法为在所有 $n$ 个点的不同的有标号的树中，等概率地随机选取一棵树。两个树是不同的当且仅当存在一条边 $(u,v)$ 只出现在其中一棵树中。比如 $(1,2),(1,3)$ 和 $(1,2),(2,3)$ 是两棵不同的树。

小 Y 用这四种方法生成了很多棵 $n$ 个节点的树，但她忘记了这些树分别由哪种方法生成的。你能帮帮她辨认这些树由哪种随机方法生成吗？

在这个题目中令 $n=1000$，也就是小 Y 生成的树的节点个数都为 $1000$。

输入格式

第一行包含 $1$ 个正整数 $T$，表示是第 $T$ 组测试数据。

接下来一个正整数 $m$，表示有 $m$ 棵树。

对于每棵树，共 $n-1$ 行。每行包含 $2$ 个正整数 $u,v$，表示这棵树中有一条节点 $u$ 与节点 $v$ 之间的边。

输出格式

输出共 $m$ 行，每行一个 $1$ 到 $4$ 之间的正整数，表示这棵树随机生成的方式。

数据范围与提示

对于所有的测试数据，保证输入的树是由上述四种方式随机生成。 各测试点满足以下约定：

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

评分方式

对于每个测试点，有 $10$ 个评分参数 $a_{10},a_9,a_8,…,a_1$。

如果你的输出中错误的答案个数为 $x$, 那么你将获得 $2s$ 的分数，其中 $s$ 为满足 $x \leq a_s$ 最大的整数。如果 $x>a_1$，那么你将获得 $0$ 分。

如果输出格式有异常你将同样获得 $0$ 分，请确保你的输出中共有 $m$ 行，每行为一个 $1$ 到 $4$ 之间的正整数。

对于每个测试点的具体评分参数见附加文件中的 scores。