[BJOI2014]想法

题目描述

小强和阿米巴是好朋友。小强要出一套题目。 他的题目以涉及面广(偏)、考察深入(怪)、思维强度大(难)著称。他为了出题,一共攒了 $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$ 到 $M$。之后,小强组合来的第一个题编号为 $M+1$,组合出来的第二个题编号为 $M+2$,依次类推。

输出格式


**本题使用 Special Judge。** $N-M$ 行,每行一个整数表示小强组合出来的每个题都涉及了几个想法。

输入输出样例

输入样例 #1

6 3
1 2
2 3
4 5

输出样例 #1

2
2
3

说明

对于 $100\%$ 的数据,$1 \le M \le 10^5$,$1 \le N \le 10^6$。 如果其中你有 $95\%$ 以上的行的答案和正确答案的误差不超过 $25\%$,那么你就可以得到分数。 所谓误差不超过 $25\%$,即如果正确答案是 $X$,那么你的答案在 $[0.8X,1.25X]$ 这个闭区间内就算误差不超过 $25\%$。