P4230 连环病原体

### （一）洞穴 顺着狭窄倾斜的溶洞向下走，这里，真有一番地心探险的感觉呢。 告诉你啊，地底有一片广阔的大世界，叫做旧地狱。 那里居住着被地面上的人厌恶的妖怪们。 虽然听着比较吓人，但实际上在地狱废弃后，一切都是井井有条的。 前方有一片开阔的空间啊，好像有人。 "地面上的来客吗,你好啊" 终于遇到地底的居民了。 眼前的两只妖怪是黑谷山女和琪斯美。 琪斯美呆在一个小桶里，悬挂在空中，和山女讨论着什么。 "哇，你们在讨论什么啊" "嗯，有关病毒的问题，你们不懂的" 忘记说了，山女可以操纵疾病，所以谈论这样的话题自然也就很平常了。 不过好奇心很难抵挡啊，那就假装自己能帮上忙，然后接着问下去吧。 "好吧，你们要是能帮上忙的话就再好不过了" "嗯，主要是，想知道病原体之间的相互作用，会对疾病产生什么影响呢。你看啊，把不同种的病原体看做点，相互作用看成连接这些点的线，如果产生了环，那么病毒的威力就会大幅加强，我把它叫做加强环。" "病原体之间的相互作用也有很多种呢，我想研究的是，每种相互作用在产生加强环的过程中有多么重要。" 啊，听起来好复杂，不过如果帮了她的忙，地底的妖怪们大概会对我们友善一些吧。 而且，点，边，环？这些名词似乎见过呢，说不定我真的能帮上忙？ 那么，继续详细地询问吧。 嗯，问出来的信息已经记录在这张纸上了。

问题摘要: 有 $n$ 种病原体，它们之间会产生 $m$ 种无方向性的影响，第 $i$ 种影响发生在 $u_i,v_i$ **两种**病原体之间。 我们把所有的**影响**按编号顺序排成一个序列，如果某一个区间包含有环，那么这个区间被称作加强区间。 求每种影响分别在多少个加强区间中出现过。 那么，到底怎样做才能高效的得出结果呢？ (后续剧情见本题题解，接下来请看 T2)

第一行一个数 $m$，接下来 $m$ 行每行两个数 $u_i,v_i$，用空格分隔

一行 $m$ 个数字，第 $i$ 个数字代表第 $i$ 种影响在多少个加强区间内出现过，数字之间用空格分隔。

### 样例解释 第一种影响在 $[1,4]$ 和 $[1,5]$ 两个加强区间内出现， 第二种影响在 $[1,4]$、$[1,5]$ 和 $[2,5]$ 三个加强区间内出现， 第三种影响在 $[1,5]$、$[1,4]$ 和 $[2,5]$ 三个加强区间内出现， 第四种影响在 $[1,4]$、$[2,5]$ 和 $[1,5]$ 三个加强区间内出现， 第五种影响在 $[2,5]$ 和 $[1,5]$ 两个加强区间内出现。 注意：加强区间是由“影响”构成的，而不是由“病原体”构成的。 对于所有测试点，$n \le 2m \le 400000$。 测试点 $1 \sim 2$ 总分 $10$ 分，$m \le 5$； 测试点 $3 \sim 6$ 总分 $20$ 分，$m \le 200$； 测试点 $7 \sim 12$ 总分 $30$ 分，$m \le 5000$； 测试点 $13 \sim 15$ 总分 $15$ 分，$m \le 50000$； 测试点 $16 \sim 18$ 总分 $15$ 分，$m \le 50000$，捆绑测试； 测试点 $19 \sim 22$ 总分 $10$ 分，$m \le 200000$，捆绑测试。 by oscar