#P18168. Challenge Matrix Multiplication

Challenge Matrix Multiplication

Challenge Matrix Multiplication

对于一个有向无环图,计算每个顶点能够到达的顶点数通常不容易。Little tarjen 声称自己有一种几乎线性的算法,并生成了大量测试图。

你发现他的图都满足一条特殊限制。设顶点 ii 的入度和出度分别为 ini\mathrm{in}_i、outi\mathrm{out}_i,则

$$\sum_{i=1}^{n}|\mathrm{in}_i-\mathrm{out}_i|\le120.$$

请利用这个限制解决问题:对每个顶点 uu,求从 uu 出发能够到达的不同顶点数 rur_u,包括 uu 自身。

输入格式

第一行两个整数 n,mn,m(2≤n≤1062\le n\le10^6,1≤m≤1061\le m\le10^6)。

接下来 mm 行,每行两个整数 u,vu,v(1≤u<v≤n1\le u<v\le n),表示有一条从 uu 到 vv 的有向边。

保证上述度数差的绝对值之和不超过 120。允许重边,图不一定连通。重边仍是不同的边,因此应分别计入入度和出度;统计可达顶点时,每个顶点只计一次。

输出格式

输出一行 nn 个整数,依次表示 r1,r2,…,rnr_1,r_2,\ldots,r_n。

样例 1

输入:

4 6
1 3
2 3
2 4
1 2
1 3
1 3

输出:

4 3 1 1

样例 2

输入:

5 7
1 4
1 5
1 2
2 4
3 4
2 5
1 4

输出:

4 3 2 1 1