공중도시 |
---|
서기 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\)개의 줄에 걸쳐 각 줄에는 다리로 직접 연결된 두 도시 \(C_1\)과 \(C_2\)가 차례대로 주어진다. 이때 \(1≤C_1,C_2≤N\)이다. 주어진 다리를 이용하여 모든 도시 사이에 이동이 가능하다. |
출력 | |
---|---|
첫 줄에는 추가로 건설할 다리의 최소 개수 \(R\)을 출력한다. 그 다음 \(R\)개의 줄에 걸쳐 각 줄에는 추가로 건설 할 다리로 직접 연결될 두 도시 \(D_1\)과 \(D_2\)를 차례 대로 출력한다. 이때 \(1≤D_1,D_2≤N\)이다. 이때 다리의 순서는 상관이 없으며, 답이 여러 가지 인 경우에는 그 중 한 가지만 출력하면 된다. |
예시 | |||
---|---|---|---|
1 | 입력 | 6 7 1 2 1 3 2 4 2 4 4 5 3 5 5 6 | |
출력 | 1 3 6 |