← 返回题目列表

AtCoder · math_and_algorithm_am

043. 是否已连接?

中文机器翻译题面 查看原题

配点 : 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.

给定的图不是连通的。