문제
서기 4,000년 현재, 지구의 황폐화로 인하여 사람들은 공중에 섬을 띄워 공중도시를 만들어 살아가고 있다.
각 공중도시는 부양무게의 한계로 작은 크기의 섬으로 만들고 대신 다리로 연결하여 모든 도시 사이에 이동이 가능하다.
아래 그림은 도시 1부터 도시 6까지 모두 6개의 공중도시가 서로 다리로 연결된 모습을 보여준다.
두 도시는 서로 다른 두 개 이상의 다리로 직접 연결될 수도 있다.
위 그림에서 도시 2와 도시 4는 서로 다른 두 개의 다리로 연결되어 있다.
그런데, 간혹 발생하는 천재지변 때문에 다리가 끊어질 가능성이 있다.
위 그림에서 도시 5와 도시 6을 잇는 다리가 하나 끊어진다면 도시 6에서는 다른 도시로 이동할 수가 없지만,
도시 1과 도시 3을 잇는 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다.
그래서 하나의 다리가 끊어지더라도 여전히 모든 두 도시 사이에 이동이 가능하도록 다리를 추가로 건설하려고 한다.
위 그림의 예에서는 다음 그림과 같이 도시 3과 도시 6을 잇는 다리를 하나 추가로 건설하면 임의의 다리가 하나 끊어지더라도
여전히 모든 도시 사이에 이동이 가능하다.
물론 도시 3 대신 다른 도시와 도시 6을 잇는 다리를 하나 추가해도 가능하다.
공중도시와 현재 상태의 다리가 주어져 있을 때, 임의의 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능할 수 있도록
다리의 길이에 상관없이 추가로 건설해야할 다리의 최소 개수와 그 위치를 찾는 프로그램을 작성하시오.
입력
다음 정보가 표준 입력으로 주어진다.
첫 줄에는 도시의 개수 N과 다리의 개수 M이 주어진다. 두 값의 범위는 3 ≤ N ≤ 100,000, N-1 ≤ M ≤ 200,000 이다.
그 다음 M개의 줄에 걸쳐 각 줄에는 다리로 직접 연결된 두 도시 C1과 C2가 차례대로 주어진다. 이때 1 ≤ C1, C2 ≤ N이다.
주어진 다리를 이용하여 모든 도시 사이에 이동이 가능하다.
다리의 개수가 도시의 개수보다 하나 작은 경우만 풀어도 30%의 점수를 받을 수 있다.
출력
다음 정보를 표준 출력으로 출력한다.
첫 줄에는 추가로 건설할 다리의 최소 개수 R을 출력한다.
그 다음 R개의 줄에 걸쳐 각 줄에는 추가로 건설할 다리로 직접 연결될 두 도시 D1과 D2를 차례대로 출력한다. 이때 1 ≤ D1, D2 ≤ N 이다.
이때 다리의 순서는 상관이 없으며, 답이 여러 가지인 경우에는 그 중 한 가지만 출력하면 된다.
예제1
67
12
13
24
24
45
35
56
1
36
예제2
33
12
13
23
0
예제3
910
12
23
23
34
45
46
36
67
68
89
2
15
79