1523 SPF

原文

時間制限: 1000MS
メモリ制限: 10000K

問題文

下図のようなネットワークを考える。ネットワーク内ではデータは各ノードを結ぶ双方向のケーブルのみを通って移動する。図左のネットワークにおいてノード3に不具合が発生して通信が不可能になった場合、これまで通信ができていた2つのノードが通信できなくなる。ノード1とノード2は問題なく通信が可能で、ノード4とノード5も問題なく通信が可能だが、それ以外のペアは通信することができない。
このようなとき、ノード3のことを単一障害点(Single Point of Failure: SPF)と呼ぶ。正確にいえば、あるノードが不具合を起こした際、それまで通信できていたペアのうち1つでも通信が不可能になるペアが出る場合、そのノードをSPFということにする。図右のネットワークにおいてはそのようなノードが存在しない、すなわちSPFが存在しないことに注意せよ。図右のネットワークにおいては、通信に障害が発生するのに最低2つのノードが壊れなければならない。

入力

入力はいくつかのネットワークからなる。ひとつのネットワークはいくつかの整数のペアからなる。1行の1つのペアが書かれており、ケーブルのつなぐ2つのノードの番号が書かれている。ペアにおける番号の順番は関係ない、すなわち 1 2 と 2 1 は同じ意味である。また、すべてのノードの番号は1から1000までの整数である。0のみからなる行はひとつのネットワークの情報が終わりということを意味する。空のネットワークは入力の終了を意味する。入力中の空行は無視せねばならない。

出力

入力にあるそれぞれのネットワークについて、その番号とSPFのリストを出力せよ。
1つ目のネットワークは "Network #1"、2つ目のネットワークは "Network #2" ... という風に識別される。ネットワーク中のSPFそれぞれについて1行出力せよ。出力形式は出力例に従い、それぞれSPFノードの番号と、そのノードが不通となることによりネットワークがいくつのサブネットワークに分断されるか、その数を出力せよ。もしネットワークにSPFが存在しなければ、SPFノードのリストのかわりに "No SPF nodes" と出力せよ。

入力例

1 2
5 4
3 1
3 2
3 4
3 5
0

1 2
2 3
3 4
4 5
5 1
0

1 2
2 3
3 4
4 6
6 3
2 5
5 1
0

0

出力例

Network #1
  SPF node 3 leaves 2 subnets

Network #2
  No SPF nodes

Network #3
  SPF node 2 leaves 2 subnets
  SPF node 3 leaves 2 subnets

出典

Greater New York 2000