Informatica Online Judge

  도망쳐! [2414 / 096E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 9   Total Tried : 52


The Champion of this Problem (C++) : gs18050 - ms / 1518byte
My Best Submission (C++) : N/A

[36th 이민규 (gs18080)]
Writer ID : [gs18080]

Background

아기 은수는 무서운 보라색 괴물로부터 영문도 모른 채 괴물의 저택에서 도망치는 중이다. 괴물의 저택은 N개의 방들과, 방과 방 사이를 잇는 총 M 개의 복도로 이루어져 있다. 신기하게도, 괴물의 저택은 아래 3가지 특징을 가지고 있다.
1. 한 방에서 다른 모든 방으로 이동할 수 있음이 보장되지 않는다.
2. 두 방을 연결하는 복도가 두개 이상 존재하지도 않는다.
3. 자기 자신으로 연결되는 복도는 존재하지 않는다.



아기 은수와 괴물의 이동속도는 정확히 같기 때문에, 괴물의 저택에서 사이클을 찾은 다음 그 사이클 안에서 영원히 버티려고 한다. 따라서 필수적으로 식량을 비축해야 한다.



이 문제에서 "사이클"이란 모든 방을 한번씩만 방문해서 만들어지는 회로를 뜻한다. 따라서 아래의 예시는 커다란 하나의 사이클이 아닌 두개의 사이클로 보아야 한다. (단순 사이클이라고도 부른다)

아기 은수는 사이클을 돌면서 식량을 먹을 수 있도록 "복도"에 식량을 저장하려고 한다. 이때 "안전"한 복도란 오직 한 개의 사이클에만 포함되는 복도를 말한다. 식량은 많을수록 좋기에, 아기 은수를 위해 식량을 저장할 복도를 모두 구해주자!

Input

첫 줄에 방의 개수 N과 복도의 개수 M이 주어진다.(1<=N<=100 000,0<=M<=200 000)
그 다음 i+1~i+M 번째 줄에는 i번째 복도가 연결하는 두 개의 방의 번호가 주어진다.

Output

첫째 줄에 식량을 저장할 복도의 개수를 출력한다.
두번째 줄에 식량을 저장할 복도의 번호를 오름차순으로 출력한다.

IO Example

입력 예시

6 7
1 2
2 3
3 1
2 4
4 5
5 2
1 6

출력 예시
6
1 2 3 4 5 6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]