← 返回题目列表

AtCoder · tkppc2016_h

H. 调试

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

問題文

Joisino-neechan 的下一个工作是帮助调试器。
调试器之前发现了一个错误,但忘记了重现该错误的详细条件。
因此,我正在考虑尝试所有符合我记得的条件的方法。

条件如下。

  • 这个游戏有N村庄和M有两条道路连接两个不同的村庄。如果不走这些道路,就无法从一个村庄到达另一个村庄。
  • 在村里1〜N,直接连接任意两个村庄的道路数量为1或更少。
  • 当bug再次出现时,从某个村庄开始,从那里出发。4他多次搬到不同的村庄。
  • 此时,同村2我从来没有经过过一次以上。
  • 为了估计调试时间,我想知道对于每个村庄,如果我最初在那个村庄,会有多少条可能的旅行路线。
    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直接连接。

    配点

    针对此问题设置了部分分数。

  • 数据集1是 可以表示为N(1≦N≦100)并且回答正确,10点。
  • 数据集2没有额外的限制,如果你回答正确,130点。
  • 出力

    输出是 由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可以选择以下旅行路线。 有

  • 1→2→3→4→5
  • 1→2→3→5→4
  • 1→2→3→5→6
  • 1→2→5→3→4
  • 1→2→5→4→3
  • 1→5→2→3→4
  • 1→5→4→3→2

  • 入力例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