H - デバッグ（Debug） Editorial /

Time Limit: 2.5 sec / Memory Limit: 256 MB

問題文

joisinoお姉ちゃんの次の仕事は、デバッガーを助けることである。
デバッガーは、先ほどあるバグを発見したのだが、再現する詳しい条件を忘れてしまった。
そこで、覚えている条件にあう方法をすべて試そうと考えている。

条件は、以下のとおりである。

  • このゲームにはN個の村と、M個の、異なる二つの村をつなぐ双方向に通行可能な道がある。これらの道を通らずに、ある村から別の村へ行く方法はない。
  • 村には1〜Nの番号がついており、また、どの二つの村についても、その間を直接結ぶ道の個数は1個以下である。
  • バグが再現した時は、ある村からスタートし、そこから4回、違う村へと移動していた。
  • この時、同じ村を2度以上通ることはなかった。

    • デバッグの時間を見積もるため、すべての村について、最初にその村にいた場合、考えられる移動経路が何通りあるかを知りたい。
    joisinoお姉ちゃんの仕事は、すべての村について、最初にその村にいた場合、考えられる移動経路が何通りあるかを求めるプログラムを作ることである。

    入力

    入力は以下の形式で標準入力から与えられる。

    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