A62 - Depth First Search Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

各頂点に 1,2,\dots,N の番号がついた、 N 頂点 M 辺の無向グラフが与えられます。
i 番目の辺は頂点 A_i と頂点 B_i とを結んでいます。
このグラフ全体が連結であるかどうか判定して以下のように出力してください。

  • もしグラフ全体が連結であれば、 The graph is connected. と出力する
  • そうでなければ、 The graph is not connected. と出力する

制約

  • 入力はすべて整数
  • 1 \le N \le 10^5
  • 0 \le M \le \min(10^5,\frac{N(N-1)}{2})
  • 1 \le A_i < B_i \le N
  • グラフに多重辺や自己ループは存在しない

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

問題文中の指示通り出力せよ。


入力例 1

3 2
1 3
2 3

出力例 1

The graph is connected.

与えられたグラフは連結です。


入力例 2

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

出力例 2

The graph is not connected.

与えられたグラフは連結ではありません。