#P4529. [Bjoi2014]想法
[Bjoi2014]想法
[BJOI 2014] 想法
题目描述
小强和阿米巴是好朋友。小强打算出一套题目。他的题目以涉及面广、考察深入、思维强度大著称。为了出题,他积攒了 个本质不同的想法,每个想法各形成一道题。他觉得直接用这些题考察选手会让比赛太难,于是请阿米巴帮忙调整。
阿米巴提出,可以把两道题组合成一道新题。新题涉及的想法集合就是原来两道题的想法集合的并集。已经组合过的题还能参与后续组合,原有题目也可以重复使用。
例如,有三个想法 ,分别对应题目 。
- 将 组合得到 ,涉及的想法是 。
- 将 组合得到 ,涉及的想法是 。
- 将 组合得到 ,涉及的想法是 。
给定每道题的组合过程,求每道组合题涉及的不同想法数。本题使用特殊评测,允许对集合大小作近似估计。
输入格式
第一行输入两个整数 ,分别表示题目总数和初始的想法数。,。
最初的 道题编号为 到 ,各只涉及一个不同的想法。接下来 行,每行输入两个已经出现的题目编号。按顺序,第 行用这两道题组合出编号为 的新题。
输出格式
按编号从小到大输出 行。每行输出一个整数,表示相应组合题涉及的不同想法数,可以是估计值。单行与参考值 比较时,落在闭区间 内视为符合误差要求。 全部 项中,至少 必须符合该要求。 全部 项中,至少 必须符合该要求。
样例
6 3
1 2
2 3
4 5
2
2
3