H - デバッグ（Debug） Editorial

Time Limit: 2.5 sec / Memory Limit: 256 MB

問題文

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

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

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

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

    入力

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

    NN MM
A1A_1 B1B_1
A2A_2 B2B_2
:
AMA_M BMB_M
    • 11行目には、村の数を表す整数N(1≦N≦105)N(1 ≦ N ≦ 10^5)と、道の数を表す整数M(1≦M≦105)M(1 ≦ M ≦ 10^5)が与えられる。
    • 続くMM行のうちii行目には、整数Ai(1≦Ai≦N),Bi(1≦Bi≦N)A_i(1≦A_i≦N),B_i(1≦B_i≦N)が書かれており、これは、ii本目の道が、村AiA_iと村BiB_iを直接つないでいることを表す。

    配点

    この問題には部分点が設定されている。

  • データセット11は、N(1≦N≦100)N(1≦N≦100)を満たし、正解すると1010点が得られる。
  • データセット22では追加の制約はなく、正解すると130130点が得られる。

    • 出力

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

    入力例1Copy

    Copy
    6 8
1 2
2 3
5 2
1 5
3 4
5 3
5 6
5 4

    出力例1Copy

    Copy
    7
4
4
7
2
4

    例えば、最初村11にいた場合には、以下の77通りの移動経路が考えられる。

  • 1→2→3→4→51→2→3→4→5
  • 1→2→3→5→41→2→3→5→4
  • 1→2→3→5→61→2→3→5→6
  • 1→2→5→3→41→2→5→3→4
  • 1→2→5→4→31→2→5→4→3
  • 1→5→2→3→41→5→2→3→4
  • 1→5→4→3→21→5→4→3→2

    • 入力例2Copy

    Copy
    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

    出力例2Copy

    Copy
    120
120
120
120
120
120

    入力例3Copy

    Copy
    8 11
3 6
7 8
8 5
4 5
2 1
2 6
3 2
4 3
5 3
6 5
7 6

    出力例3Copy

    Copy
    12
14
11
17
11
9
15
17

    2025-04-15 (Tue)
    03:16:54 +00:00