暂无测试数据。

Description

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

他的题目以涉及面广（偏）、考察深入（怪）、思维强度大（难）著称。他为了出题，一共攒了 \(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\}\)。
• 现在，小强告诉你每个题目都是如何组合而来的。你要回答的就是，每个题目涉及的想法的集合有多大。

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

Format

Input

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

Output

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

Sample 1

Input

6 3
1 2
2 3
4 5

Output

2
2
3

Limitation

Data

• 对于 \(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\)。

Special Judge

本题使用 Special Judge。

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

Time and Space

2s, 125MB.

Source

BJOI 2014