AT_tkppc2016_h デバッグ（Debug）

[problemUrl]: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_h joisinoお姉ちゃんの次の仕事は、デバッガーを助けることである。 デバッガーは、先ほどあるバグを発見したのだが、再現する詳しい条件を忘れてしまった。 そこで、覚えている条件にあう方法をすべて試そうと考えている。 条件は、以下のとおりである。 3. このゲームには$ N $個の村と、$ M $個の、異なる二つの村をつなぐ双方向に通行可能な道がある。これらの道を通らずに、ある村から別の村へ行く方法はない。 4. 村には$ 1〜N $の番号がついており、また、どの二つの村についても、その間を直接結ぶ道の個数は$ 1 $個以下である。 5. バグが再現した時は、ある村からスタートし、そこから$ 4 $回、違う村へと移動していた。 6. この時、同じ村を$ 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 $を直接つないでいることを表す。

出力は$ N $行からなる。 $ i $行目には、最初に村$ i $にいた場合、考えられる移動経路が何通りあるかを出力せよ。

### 配点 この問題には部分点が設定されている。 3. データセット$ 1 $は、$ N(1≦N≦100) $を満たし、正解すると$ 10 $点が得られる。 4. データセット$ 2 $では追加の制約はなく、正解すると$ 130 $点が得られる。 ### Sample Explanation 1 例えば、最初村$ 1 $にいた場合には、以下の$ 7 $通りの移動経路が考えられる。 2. $ 1→2→3→4→5 $ 3. $ 1→2→3→5→4 $ 4. $ 1→2→3→5→6 $ 5. $ 1→2→5→3→4 $ 6. $ 1→2→5→4→3 $ 7. $ 1→5→2→3→4 $ 8. $ 1→5→4→3→2 $