Description

问题摘要:

有n 种病原体，它们之间会产生$m$种无方向性的影响，第$i$种影响发生在$u_i$,$v_i$ 两种病原体之间。

我们把所有的影响按编号顺序排成一个序列，如果某一个区间包含有环，那么这个区间被称作加强区间。

求每种影响分别在多少个加强区间中出现过。

那么，到底怎样做才能高效的得出结果呢？

(后续剧情见本题题解，接下来请看T2)

Input Format

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

Output Format

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

5
1 2
2 3
3 4
1 4
4 2

2 3 3 3 2

Hint

###样例解释：

第一种影响在[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\leqslant2m\leqslant400000$

测试点1~2总分10分，$m\leqslant5$

测试点3~6总分20分，$m\leqslant200$

测试点7~12总分30分，$m\leqslant5000$

测试点13~15总分15分，$m\leqslant50000$

测试点16~18总分15分，$m\leqslant50000$，捆绑测试

测试点19~22总分10分，$m\leqslant200000$，捆绑测试

by oscar