C0555 [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}$。

现在，小强告诉你每个题目都是如何组合而来的。你要回答的就是，每个题目涉及的想法的集合有多大。

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

样例输入 1

6 3
1 2
2 3
4 5

样例输出 1

2
2
3