← 返回题目列表

Codeforces · 1268/E

E. 快乐仙人掌

中文机器翻译题面 查看原题

给你一张仙人掌图,在该图中,每条边最多位于一个简单的循环上。

给出为 $$$m$$$ 边 $$$a_i, b_i$$$,第 $$$i$$$ 边的权重为 $$$i$$$。

如果仙人掌中的一条路径的边权重不断增加,我们称该路径为增加路径。

如果存在一条从 $$$u$$$ 开始并以 $$$v$$$ 结束的递增路径,我们称一对顶点为 $$$(u,v)$$$ 快乐。

对于每个顶点 $$$u$$$ 找到其他顶点 $$$v$$$ 的数量,这样 $$$(u,v)$$$ 是快乐的。

输入

输入的第一行包含两个整数 $$$n,m$$$ ($$$1 \leq n, m \leq 500\,000$$$):给定仙人掌中的顶点和边的数量。

接下来的 $$$m$$$ 行包含仙人掌边缘的描述,其中 $$$i$$$ 包含两个整数 $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$)。

保证不存在重边并且图是连通的。

输出

打印 $$$n$$$ 整数,顶点 $$$1,2,\ldots,n$$$ 所需的值。

示例

输入 #1

3 3
1 2
2 3
3 1

输出 #1

2 2 2

输入 #2

5 4
1 2
2 3
3 4
4 5

输出 #2

4 4 3 2 1