Where's My Internet??

Photo by Jerry John
from Flickr

A new town is being built far out in the country, and currently there are $N$ houses. People have already started moving in. However, some of the houses aren’t connected to the internet yet, and naturally residents are outraged.

The houses are numbered $1$ to $N$. House number $1$ has already been connected to the internet via a long network cable to a neighboring town. The plan is to provide internet to other houses by connecting pairs of houses with separate network cables. A house is connected to the internet if it has a network cable to another house that’s already connected to the internet.

Given a list of which pairs of houses are already connected by a network cable, determine which houses are not yet connected to the internet.

The first line of input contains two integers $1 \leq N,M \leq 200\, 000$, where $N$ is the number of houses and $M$ is the number of network cables already deployed. Then follow $M$ lines, each containing a pair of distinct house numbers $1 \leq a, b \leq N$ meaning that house number $a$ and house number $b$ are already connected by a network cable. Each house pair is listed at most once in the input.

If all the houses are already connected to the internet,
output one line containing the string `Connected`. Otherwise, output a list of house
numbers in increasing order, one per line, representing the
houses that are not yet connected to the internet.

Sample Input 1 | Sample Output 1 |
---|---|

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

Sample Input 2 | Sample Output 2 |
---|---|

2 1 2 1 |
Connected |

Sample Input 3 | Sample Output 3 |
---|---|

4 3 2 3 4 2 3 4 |
2 3 4 |