시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB110504851.064%

문제

2039년, 디미고에는 $1$번부터 $N$번까지의 번호가 매겨진 $N$개의 건물과 이 건물들을 잇는 $M$개의 길이 있다. 두 건물을 직접 연결하는 길은 $1$개 이하이다.

어느 날 학교에 바이러스가 돌게 되어 전교생이 바이러스에 감염될 위기에 처했다. 이에 당신은 바이러스의 전파를 막기 위해 다음과 같은 통제 작업을 $0$회 이상 진행하여 모든 길을 통제하기로 했다.

  • 아직 통제되지 않은 길과 직접 연결된 건물 하나를 선택한 뒤 그 건물과 직접 연결된 모든 길을 통제한다.

학생들의 안전을 위해 당신은 통제 작업을 최대한 많이 진행하기로 했다. 이때 통제 작업을 어떤 순서로 진행해야 하는지 구하시오.

입력

첫 번째 줄에 건물의 개수 $N$, 길의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10^{5};$ $0 \le M \le 10^{5})$

두 번째 줄부터 $M$개의 줄에 걸쳐 각 줄에 길이 연결하는 두 건물의 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N;$ $u \ne v)$

출력

첫 번째 줄에 통제 작업을 진행할 수 있는 최대 횟수 $K$를 출력한다.

두 번째 줄부터 $K$개의 줄에 걸쳐 각 줄에 통제 작업을 진행할 건물의 번호를 순서대로 한 줄에 하나씩 출력한다.

통제 작업의 횟수를 최대화하는 방법이 여러 가지라면 그중 아무거나 하나를 출력한다.

예제 입력 1

3 3
3 2
3 1
2 1

예제 출력 1

2
2
3

예제 입력 2

10 8
4 10
10 7
1 4
8 6
10 1
1 9
7 4
9 5

예제 출력 2

6
7
10
4
5
9
8