공중도시

서기 4000년, 지구가 황폐해지면서 사람들은 공중에 섬을 띄우고 그 위에 도시를 세워 살아간다. 섬 하나가 버틸 수 있는 무게에 한계가 있어서 도시는 작게 만들고, 대신 도시 사이를 다리로 이어 어느 도시에서든 다른 모든 도시로 이동한다. 아래 그림은 도시 1부터 도시 6까지 여섯 개의 공중도시가 다리로 이어진 모습이다.

서로 다른 다리 두 개 이상이 같은 두 도시를 직접 잇기도 한다. 위 그림에서 도시 2와 도시 4는 서로 다른 다리 두 개로 이어져 있다.

천재지변으로 다리가 끊어지는 일이 가끔 생긴다. 위 그림에서 도시 5와 도시 6을 잇는 다리가 끊어지면 도시 6에서는 어느 도시로도 갈 수 없다. 반면 도시 1과 도시 3을 잇는 다리가 끊어져도 모든 도시 사이의 이동은 그대로 유지된다.

그래서 다리 하나가 끊어져도 모든 도시 사이의 이동이 유지되도록 다리를 더 놓으려고 한다. 위 그림에서는 다음 그림처럼 도시 3과 도시 6을 잇는 다리 하나만 더 놓으면 어떤 다리가 끊어져도 모든 도시 사이를 오갈 수 있다. 도시 3 대신 다른 도시와 도시 6을 이어도 된다.

공중도시와 지금 놓인 다리가 주어질 때, 다리 하나가 끊어져도 모든 도시 사이의 이동이 유지되도록 더 놓아야 하는 다리의 최소 개수와 그 위치를 구하는 프로그램을 작성하시오. 다리의 길이는 따지지 않는다.

첫 줄에 도시의 개수 $N$과 다리의 개수 $M$이 주어진다. $3 \le N \le 100{,}000$, $N-1 \le M \le 200{,}000$이다. 다음 $M$개의 줄에는 다리로 직접 이어진 두 도시 $C_1$과 $C_2$가 차례대로 주어진다. $1 \le C_1, C_2 \le N$이다. 주어진 다리만으로 모든 도시 사이의 이동이 가능하다.

첫 줄에 더 놓아야 하는 다리의 최소 개수 $R$을 출력한다. 다음 $R$개의 줄에는 새로 놓을 다리가 직접 잇는 두 도시 $D_1$과 $D_2$를 작은 번호부터 출력한다.

최소 개수를 이루는 방법이 여러 가지일 수 있으므로, 다음 규칙으로 정해지는 답 하나만 출력한다.

1. 다리 하나를 없앴을 때 서로 오갈 수 없는 도시 쌍이 생기면 그 다리를 절단 다리라고 하자. 절단 다리를 모두 없애면 도시가 여러 덩어리로 나뉜다. 각 덩어리를 블록이라 하고, 블록의 번호는 그 블록에 속한 도시 번호 중 가장 작은 값으로 한다.
2. 블록을 정점으로, 절단 다리를 간선으로 삼으면 트리가 된다. 도시 1이 속한 블록을 뿌리로 하고, 각 블록에서 자식 블록을 번호가 작은 쪽부터 방문하는 깊이 우선 탐색을 한다. 방문한 순서대로, 트리에서 이웃 블록이 하나뿐인 블록만 골라 $l_1, l_2, \dots, l_L$이라 하자.
3. $k = \lceil L/2 \rceil$이라 하자. $i = 1, 2, \dots, L-k$의 순서대로 $l_i$의 번호와 $l_{i+k}$의 번호를 잇는 다리를 한 줄에 하나씩 출력한다. $L$이 홀수이면 마지막 줄에 $l_k$의 번호와 $l_1$의 번호를 잇는 다리를 출력한다.
4. 절단 다리가 하나도 없으면 $R = 0$이고, 첫 줄 뒤에는 아무것도 출력하지 않는다.