問題文
Joisino-neechan 的下一个工作是帮助调试器。
调试器之前发现了一个错误,但忘记了重现该错误的详细条件。
因此,我正在考虑尝试所有符合我记得的条件的方法。
条件如下。
为了估计调试时间,我想知道对于每个村庄,如果我最初在那个村庄,会有多少条可能的旅行路线。
Joisino-chan 的工作是创建一个程序,计算每个村庄如果她首先到达该村庄,则有多少条可能的旅行路线。
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 A_2 B_2 : A_M B_M
- 1行包含一个代表村庄数量的整数。N(1 ≦ N ≦ 10^5)和一个表示路径数量的整数M(1 ≦ M ≦ 10^5)。 表示
- 继续M行i行包含一个整数A_i(1≦A_i≦N),B_i(1≦B_i≦N),即i真正的路是村庄A_i和村庄B_i直接连接。
配点
针对此问题设置了部分分数。
出力
输出是
由N行组成。
i一线村
如果你在i,输出有多少条可能的旅行路线。
入力例1
6 8 1 2 2 3 5 2 1 5 3 4 5 3 5 6 5 4
出力例1
7 4 4 7 2 4
例如第一个村 如果您位于1,请使用以下命令7可以选择以下旅行路线。 有
入力例2
6 15 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
出力例2
120 120 120 120 120 120
入力例3
8 11 3 6 7 8 8 5 4 5 2 1 2 6 3 2 4 3 5 3 6 5 7 6
出力例3
12 14 11 17 11 9 15 17