小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}$