A6301 | 「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$ 之间的正整数，表示这棵树随机生成的方式。