단절선

면접 대비

시간 제한1초메모리 제한256 MB

요약
연결된 무방향 그래프의 모든 브리지를 찾아 끝점 순서대로 정렬해 출력합니다.
난이도

보통10점 중 4점

유형
DFS, 그래프
정답자
아직 제출이 없습니다

문제

그래프가 주어졌을 때 단절선을 모두 찾아 출력하는 프로그램을 작성하시오.

단절선은 그 간선을 지웠을 때 그래프가 두 개 이상으로 나누어지는 간선이다. 즉, 지웠을 때 그래프의 연결 요소 개수가 늘어나는 간선이다.

입력

첫째 줄에 정점의 개수 VV와 간선의 개수 EE가 주어진다. (1≤V≤100 0001 \le V \le 100\,000, 1≤E≤1 000 0001 \le E \le 1\,000\,000)

다음 EE개 줄에는 간선을 나타내는 두 정수 AA, BB가 주어진다. AA번 정점과 BB번 정점이 연결되어 있다는 뜻이고, 간선은 양방향이다.

그래프는 항상 연결되어 있고, 같은 간선이 두 번 이상 주어지는 경우는 없다. AA와 BB가 같은 경우도 없다. 정점 번호는 11부터 VV까지의 자연수이다.

출력

첫째 줄에 단절선의 개수 KK를 출력한다.

둘째 줄부터 KK개 줄에 단절선을 한 줄에 하나씩 출력한다. 각 간선은 A B 형식으로, A<BA < B를 만족하도록 출력한다. AA가 작은 것부터 출력하고, AA가 같으면 BB가 작은 것부터 출력한다. 같은 간선은 한 번만 출력한다. KK가 0이면 첫째 줄만 출력한다.

예제7

  1. 예제 1

    입력
    7 8
1 4
4 5
5 1
1 6
6 7
2 7
7 3
2 3
    예상 출력
    2
1 6
6 7

  2. 예제 2

    입력
    2 1
1 2
    예상 출력
    1
1 2

  3. 예제 3

    입력
    5 5
1 2
2 3
3 4
4 5
5 1
    예상 출력
    0

  4. 예제 4

    입력
    5 4
1 2
2 3
3 4
4 5
    예상 출력
    4
1 2
2 3
3 4
4 5

  5. 예제 5

    입력
    7 6
2 1
3 1
4 1
5 1
6 1
7 1
    예상 출력
    6
1 2
1 3
1 4
1 5
1 6
1 7

  6. 예제 6

    입력
    6 7
1 2
2 3
3 1
4 5
5 6
6 4
3 4
    예상 출력
    1
3 4

  7. 예제 7

    입력
    13 14
1 2
2 3
2 10
2 11
3 4
4 5
5 3
10 12
11 13
5 6
6 7
7 8
8 9
9 6
    예상 출력
    7
1 2
2 3
2 10
2 11
5 6
10 12
11 13