给你一张仙人掌图,在该图中,每条边最多位于一个简单的循环上。
给出为 $$$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