OpenKattis
Week 06 [converted from problem group]

Start

2017-08-02 16:00 AKDT

Week 06 [converted from problem group]

End

2018-08-02 16:00 AKDT
The end is near!
Session is over.
Not yet started.
Session is starting in -1273 days 13:17:42

Time elapsed

8760:00:00

Time remaining

0:00:00

Problem F
Where's My Internet??

/problems/wheresmyinternet/file/statement/en/img-0001.jpg
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.

Input

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.

Output

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