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

\n

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

\n

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

\n

第二种方法为首先生成一个 $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

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

\n

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

\n

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

\n

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

\n

输入格式

\n

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

\n

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

\n

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

\n

输出格式

\n

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

\n

样例一

\n

见样例数据下载。

\n

限制与约定

\n

统计

递交统计

【ZJOI2016】随机树生成器

信息

状态

开发

支持

还没有账户？

登录