#2229. 「BJOI2014」想法

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

小强和阿米巴是好朋友。小强要出一套题目。

他的题目以涉及面广(偏)、考察深入(怪)、思维强度大(难)著称。他为了出题,一共攒了 M 个本质不同的想法,每个想法形成了一个题目。不过,他觉得拿这些题目去考察选手会把比赛搞的太过变态,所以,想请阿米巴来帮忙调整一下他的题目。

阿米巴指出,为了让一场考试的题目的考察点尽量全面,有一个通用的做法叫做「组合」。如果把两个题目 A B 组合在一起,那么组合而成的题目涉及到的想法的集合就是 A 涉及到的想法的集合和 B 涉及到的想法的集合的并。

并且,题目是可以反复组合的。
例如,小强现在有三个想法 1,2,3 ,分别对应了题目 P_1,P_2,P_3
现在,小强把 P_1 P_2 组合得到 P_4 P_4 涉及的想法的集合是 \{1,2\}
之后,小强把 P_2 P_3 组合得到 P_5 P_5 涉及的想法的集合是 \{2,3\}
最后,小强把 P_4 P_5 组合得到 P_6 P_6 涉及的想法的集合是 \{1,2,3\}
现在,小强告诉你每个题目都是如何组合而来的。你要回答的就是,每个题目涉及的想法的集合有多大。

不过,这个问题是很难的。于是,你只需要能够以比较高的概率回答的比较准确即可。

输入格式

第一行两个整数 N M ,依次表示小强的题目数量和想法的数量。
接下来 N-M 行,每行两个整数,依次表示小强组合出来的题目都是由哪两个题组合而成的。 M 个想法对应的题目依次编号为 1 \sim M 。之后,小强组合出来的第一个题编号为 M+1 ,组合出来的第二个题编号为 M+2 ,依次类推。

输出格式

输出 N-M 行,每行一个整数表示小强组合出来的每个题都涉及了几个想法。

样例

样例输入

6 3
1 2
2 3
4 5

样例输出

2
2
3

数据范围与提示

对于 30\% 的数据, M\le 10^3,N\le 10^4
对于 60\% 的数据, M\le 10^4,N\le 10^5
对于所有数据, M \leq 10^5,\ N \leq 10^6

对于每个输出文件,如果其中你有 95\% 以上的行的答案和正确答案的误差不超过 25\% ,那么你就可以得到分数。所谓误差不超过 25\% ,即,如果正确答案是 X ,那么你的答案在 [0.8X,1.25X] 这个闭区间内。