#P4529. [Bjoi2014]想法

[Bjoi2014]想法

[BJOI 2014] 想法

题目描述

小强和阿米巴是好朋友。小强打算出一套题目。他的题目以涉及面广、考察深入、思维强度大著称。为了出题,他积攒了 MM 个本质不同的想法,每个想法各形成一道题。他觉得直接用这些题考察选手会让比赛太难,于是请阿米巴帮忙调整。

阿米巴提出,可以把两道题组合成一道新题。新题涉及的想法集合就是原来两道题的想法集合的并集。已经组合过的题还能参与后续组合,原有题目也可以重复使用。

例如,有三个想法 1,2,31,2,3,分别对应题目 P1,P2,P3P_1,P_2,P_3。

  • 将 P1,P2P_1,P_2 组合得到 P4P_4,涉及的想法是 {1,2}\{1,2\}。
  • 将 P2,P3P_2,P_3 组合得到 P5P_5,涉及的想法是 {2,3}\{2,3\}。
  • 将 P4,P5P_4,P_5 组合得到 P6P_6,涉及的想法是 {1,2,3}\{1,2,3\}。

给定每道题的组合过程,求每道组合题涉及的不同想法数。本题使用特殊评测,允许对集合大小作近似估计。

输入格式

第一行输入两个整数 N,MN,M,分别表示题目总数和初始的想法数。1≤M≤1051\le M\le10^5,M≤N≤106M\le N\le10^6。

最初的 MM 道题编号为 11 到 MM,各只涉及一个不同的想法。接下来 N−MN-M 行,每行输入两个已经出现的题目编号。按顺序,第 ii 行用这两道题组合出编号为 M+iM+i 的新题。

输出格式

按编号从小到大输出 N−MN-M 行。每行输出一个整数,表示相应组合题涉及的不同想法数,可以是估计值。单行与参考值 xx 比较时,落在闭区间 [0.8x,1.25x][0.8x,1.25x] 内视为符合误差要求。 全部 N−MN-M 项中,至少 90%90\% 必须符合该要求。 全部 N−MN-M 项中,至少 90%90\% 必须符合该要求。

样例

6 3
1 2
2 3
4 5
2
2
3