문제
정올광역시의 모범 택시 기사들은 정말로 놀랍다.
정올광역시에는 무려 N개의 교차로와 M개의 도로가 있는데, 모범 택시 기사들은 어떤 도로가 어떤 교차로에서 어떤 교차로로 통하는지를 모두 외우고 다닌다!
참된 프로정신 그 자체이다.
정올광역시의 모범 택시 기사가 된 진호는 운전 실력이 매우 뛰어나서 운전하는 일에는 걱정이 없다.
그러나 진호는 여러분들과 마찬가지로 단순 암기를 싫어하므로, M개의 도로를 모두 암기하는 것은 피하고 싶어한다.
그래서 진호는 최소한의 개수의 도로만 선택해서, 자신이 선택한 도로로만 다니려고 한다.
모범 택시 기사는 어떤 교차로에서 출발하든 정올광역시에 존재하는 모든 교차로로 갈 수 있어야 하므로, 진호는 그만큼의 도로는 외워야 한다.
진호는 정올광역시의 구조가 한눈에 보이는 지도를 보고, 최소한의 도로만 외울 때, 외워야 하는 도로의 번호를 알아보고자 한다.
예를 들어, 다음과 정올광역시의 구조가 그림 1과 같다고 생각해 보자.
그림 1에서 원은 교차로를 뜻하고, 선은 도로를 뜻한다. 도로 위에 써 있는 숫자는 해당 도로의 번호이다.
진호가 선택한 도로 번호가 [1, 2, 3, 4]라고 하자. 이 경우는 진호가 1번 교차로에서 5번 교차로로 갈 수 있는 방법이 아예 없으므로, 정답이 될 수 없다.
진호가 선택한 도로 번호가 [1, 2, 3, 4, 5]라고 하자. 이 경우는 진호가 어느 교차로에서 시작하든 어느 교차로로든 갈 수 있으므로, 정답의 후보가 될 수 있다.
진호가 선택한 도로 번호가 [1, 2, 3, 5]라고 하자. 이 경우 역시 어느 교차로에서 시작하든 어느 교차로로든 갈 수 있으므로, 역시 정답의 후보이다.
앞에 [1, 2, 3, 4, 5]보다 외워야 하는 도로의 개수가 적으므로, 이 경우가 더 나은 경우라고 할 수 있다.
정올광역시의 도시 구조가 주어질 때, 진호가 외워야 하는 도로 번호를 모두 출력하는 프로그램을 작성하라.
가능한 답이 여러 개 있는 경우 사전순으로 더 앞선 경우를 출력한다.
- 사전순: 두 답의 후보 [a1, a2,…ak] , [b1, b2,…bk]에 있어서, 어떤 정수 i에 대해서 a1=b1, a2=b2, … ai-1=bi-1을 만족하고, ai<bi를 만족하는 경우, [a1, a2, … ak]가 사전순으로 앞선다고 한다.
예를 들어, 그림 1의 예시에서 [1, 2, 3, 5]와 [1, 3, 5, 7]은 모두 정답의 후보지만, [1, 2, 3, 5]가 사전순으로 앞서는 경우이다.
입력
첫 줄에 교차로의 개수인 N과, 도로의 개수 M이 주어진다.
둘째 줄부터 M개의 줄에 걸쳐서, 1번 도로부터 M번 도로까지 각 도로의 정보인 si,ei가 주어진다.
이는 i번 도로가 si번 교차로와 ei번 교차로를 잇는다는 뜻이다.
어떤 두 교차로를 고르든, 한 교차로에서 다른 교차로로 갈 수 있는 경로가 최소한 하나는 존재한다.
[제약 형식]
모든 부분문제에서 1≤N≤50,000, N-1≤M≤106을 만족한다.
모든 부분문제에서 1≤si, ei≤N이고, si≠ei이다.
주어진 모든 입력값은 정수이다.
출력
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 3점 | M=N-1 |
| #2 | 14점 | N≤100, M≤500 |
| #3 | 12점 | 모든 도로에서 si<ei이다. 두 도로 i번 도로와 j번 도로를 고려할 때, i<j를 만족하면, si<sj 또는 (si=sj 그리고 ei<ej)를 항상 만족한다. |
| #4 | 28점 | N≤1,000, M≤3,000 |
| #5 | 43점 | 주어진 제약조건 외에 아무 제약조건이 없다. |
예제
5 7
1 2
4 1
2 3
3 1
4 5
5 2
1 5
4
1 2 3 5
로그인해야 코드를 작성할 수 있어요.