【ZJOI2016】随机树生成器
小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$ 之间的正整数，表示这棵树随机生成的方式。
样例一
见样例数据下载。
限制与约定
| 测试点编号 | $m$ | 约定 |
|---|---|---|
| 1 | $=2000$ | 只会出现第 $1,2$ 种生成方式 |
| 2 | $=3000$ | 只会出现第 $1,2,3$ 种生成方式 |
| 3 | 只会出现第 $1,3,4$ 种生成方式 | |
| 4 | $=4000$ | |
| 5 |
对于所有的测试数据，保证输入的树是由上述四种方式随机生成。
对于每个测试点，保证每种可能出现的生成方式恰好出现 $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。
时间限制：$3\texttt{s}$
空间限制：$256\texttt{MB}$