P4581 [BJOI2014] Ideas

Xiao Qiang and Amiba are good friends. Xiao Qiang wants to prepare a set of problems. His problems are known for broad scope (biased), deep probing (quirky), and high difficulty (hard). To prepare problems, he has collected $M$ essentially different ideas, and each idea forms a problem. However, he feels that using these problems to test contestants would make the contest too extreme, so he asks Amiba to help adjust his problems. Amiba points out a general method called “combination” to make an exam’s coverage as comprehensive as possible. If two problems $A$ and $B$ are combined, then the set of ideas involved in the resulting problem is the union of the sets of ideas involved in $A$ and $B$. Moreover, problems can be combined repeatedly. For example, suppose Xiao Qiang currently has three ideas $1, 2, 3$, corresponding to problems $P_1, P_2, P_3$ respectively: - Xiao Qiang combines $P_1$ and $P_2$ to get $P_4$. The set of ideas involved in $P_4$ is $\{1, 2\}$. - Xiao Qiang combines $P_2$ and $P_3$ to get $P_5$. The set of ideas involved in $P_5$ is $\{2, 3\}$. - Xiao Qiang combines $P_4$ and $P_5$ to get $P_6$. The set of ideas involved in $P_6$ is $\{1, 2, 3\}$. Now, Xiao Qiang tells you how each problem was formed by combination. Your task is to answer how large the set of ideas involved in each problem is. However, this problem is hard. So you only need to answer fairly accurately with a relatively high probability.

The first line contains two integers $N, M$, denoting the number of Xiao Qiang’s problems and the number of ideas, respectively. Then follow $N - M$ lines, each containing two integers, indicating which two problems were combined to form each combined problem. The $M$ ideas correspond to problems numbered $1$ through $M$. After that, the first combined problem is numbered $M + 1$, the second combined problem is numbered $M + 2$, and so on.

**This problem uses Special Judge.** Output $N - M$ lines. Each line contains one integer, which is the number of ideas involved in each combined problem.

Constraints: For $100\%$ of the testdata, $1 \le M \le 10^5$, $1 \le N \le 10^6$. If at least $95\%$ of your lines have absolute error within $25\%$ of the correct answers, you will receive points. “Error within $25\%$” means: if the correct answer is $X$, then your answer falling in the closed interval $[0.8X, 1.25X]$ counts as within $25\%$ error. Translated by ChatGPT 5