P5830 [ZJOI2016] Random Tree Generator

The additional files and samples can be downloaded from “Attachments” at the bottom of the page.

Xiao Y recently got a random number generator (random number generator). Xiao Y wants to use this random number generator to generate a tree with $n$ nodes. A tree is an undirected connected graph with no cycles. After some research, Xiao Y found $4$ random tree generation methods. The first method is: first generate a uniformly random permutation $p_1,p_2,\ldots,p_n$ of $1$ to $n$. Then for every node $i$ $(2 \leq i \leq n)$, add an edge from $p_i$ to $p_j$, where $j$ is a random integer from $1$ to $i-1$. The second method is: first generate a uniformly random permutation $p_1,p_2,\ldots,p_n$ of $1$ to $n$. Then for every node $i$ $(2 \leq i \leq n)$, add an edge from $p_i$ to $p_j$, where $j$ is a random integer from $\lfloor \frac {i}{2} \rfloor$ to $i-1$. The third method is: first start with a graph of $n$ vertices with no edges. Then repeatedly generate a pair of vertices $u,v$ uniformly at random. If $u$ and $v$ are not connected in the current graph, add the edge $(u,v)$ to the graph. Repeat this process until the graph becomes connected. The fourth method is: among all different labeled trees on $n$ vertices, choose one uniformly at random. Two trees are different if and only if there exists an edge $(u,v)$ that appears in exactly one of them. For example, $(1,2),(1,3)$ and $(1,2),(2,3)$ are two different trees. Xiao Y generated many trees with $n$ nodes using these four methods, but she forgot which method generated each tree. Can you help her identify which random method generated each tree? In this problem, let $n=1000$, meaning every tree generated by Xiao Y has $1000$ nodes.

The first line contains $1$ positive integer $T$, indicating the $T$-th set of testdata. Then an integer $m$, indicating there are $m$ trees. For each tree, there are $n-1$ lines. Each line contains $2$ positive integers $u,v$, indicating there is an edge between node $u$ and node $v$ in this tree.

Output a total of $m$ lines. Each line contains a positive integer from $1$ to $4$, indicating the random generation method of the corresponding tree.

For all testdata, it is guaranteed that the input trees are generated by the four methods above. Each test point satisfies the following rules. | Test Point | $m$ | Rule | | --- | --- | --- | | 1 | $=2000$ | Only methods $1,2$ will appear. | | 2 | $=3000$ | Only methods $1,2,3$ will appear. | | 3 | $=3000$ | Only methods $1,3,4$ will appear. | | 4 | $=4000$ | None. | | 5 | $=4000$ | None. | For each test point, it is guaranteed that each possible appearing generation method appears exactly $1000$ times. #### Scoring For each test point, there are $10$ scoring parameters $a_{10},a_9,a_8,\ldots,a_1$. If the number of wrong answers in your output is $x$, then you will get a score of $2s$, where $s$ is the largest integer satisfying $x \leq a_s$. If $x>a_1$, then you will get $0$ points. If the output format is abnormal, you will also get $0$ points. Please make sure your output has exactly $m$ lines, and each line is an integer from $1$ to $4$. For the specific scoring parameters of each test point, see `scores` in the additional files. Translated by ChatGPT 5