Graph Connectivity Check

You are given an undirected graph specified by an adjacency list. The graph is described by the number of vertices and a list of edges. Your task is to determine whether the graph is connected.

A graph \( G = (V, E) \) is said to be connected if there is a path between every pair of vertices in \( V \). Note that an empty graph (with 0 vertices) is considered connected, and a single vertex with no edges is also considered connected.

Input/Output Format:

The input is read from standard input (stdin) and the output is printed to standard output (stdout). Please ensure that your solution reads from stdin and writes to stdout.

inputFormat

The first line of input contains a single integer \( n \) representing the number of vertices in the graph. If \( n > 0 \), the second line contains a single integer \( m \) representing the number of edges. This is followed by \( m \) lines, each containing two space-separated integers \( u \) and \( v \) denoting an undirected edge connecting vertices \( u \) and \( v \). The vertices are numbered from 1 to \( n \). In the case where \( n = 0 \), there will be no further input.

outputFormat

Print a single line containing either True if the graph is connected, or False otherwise.

4
3
1 2
2 3
3 4

True