서기 4,000년 현재, 지구의 황폐화로 인하여 사람들은 공중에 섬을 띄워 공중도시를 만들어 살아가고 있다. 각 공중도시는 부양무게의 한계로 작은 크기의 섬으로 만들고 대신 다리로 연결하여 모든 도시 사이에 이동이 가능하다.

아래 그림은 도시 1부터 도시 6까지 모두 6개의 공중도시가 서로 다리로 연결된 모습을 보여준다.

두 도시는 서로 다른 두 개 이상의 다리로 직접 연결될 수도 있다. 위 그림에서 도시 2와 도시 4 는 서로 다른 두 개의 다리로 연결되어 있다. 그런데, 간혹 발생하는 천재지변 때문에 다리가 끊어질 가능성이 있다. 위 그림에서 도시 5와 도 시 6을 잇는 다리가 하나 끊어진다면 도시 6에서 는 다른 도시로 이동할 수가 없지만, 도시 1과 도 시 3을 잇는 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다.

그래서 하나의 다리가 끊어지더라도 여전히 모든 두 도시 사이에 이동이 가능하도록 다리를 추가로 건설하려고 한다. 위 그림의 예에서는 다음 그림 과 같이 도시 3과 도시 6을 잇는 다리를 하나 추 가로 건설하면 임의의 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다. 물론 도시 3 대신 다른 도시와 도시 6을 잇는 다리를 하나 추가해도 가능하다.

공중도시와 현재 상태의 다리가 주어져 있을 때, 임의의 다리가 하나 끊어지더라도 여전히 모든 도 시 사이에 이동이 가능할 수 있도록 다리의 길이 에 상관없이 추가로 건설해야할 다리의 최소 개수 와 그 위치를 찾는 프로그램을 작성하시오.

수행 시간은 1초를 넘을 수 없다. 사용하는 메모리는 128MB를 넘을 수 없다.

입력

• 첫 줄에는 도시의 개수 N 과 다리의 개수 M이 주어진다. 두 값의 범위는 3 ≤ N ≤ 100,0000, N-1 ≤ M ≤ 200,000이다.
• 그 다음 M 개의 줄 에 걸쳐 각 줄에는 다리로 직접 연결된 두 도시 C1과 C2 가 차례대로 주어진다. 이때 1 ≤ C1,C2 ≤ N 이다. 주어진 다리를 이용하여 모든 도시 사이에 이동이 가능하다.

출력

• 첫 줄에는 추가로 건설할 다리의 최소 개수 R을 출력한다.
• 그 다음 R개의 줄에 걸쳐 각 줄에는 추가로 건설 할 다리로 직접 연결될 두 도시 D1 과 D2를 차례 대로 출력한다. 이때 1 ≤D1,D2 ≤ N 이다. 이때 다리의 순서는 상관이 없으면 , 답이 여러가지 인 경우에는 그 중 한 가지만 출력하면 된다.

입출력 예

입력

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

출력

13
6

입력

3 3
1 2
1 3
2 3

출력

0

입력

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

출력

21
5
7 9

출처:koi 고등 32 회 지역본선 4/4