KOI 전국 2014 초4/중3/고2- 버스 노선 > 문제은행 : 정보올림피아드&알고리즘




2796 : 버스 노선

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
32 회   
시도횟수
157 회   

문제

국경을 따라 순환 도로를 건설한 국가가 있다. 

이 순환 도로에는 N 개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1 까지 번호가 시계방향 순서로 지정되어 있다. 

현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다.

 

각 버스 노선은 [a, b]로 표시된다. 

이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 

순환도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

 

국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 

취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 

 

예를 들어, N = 10 일 때, 5개의 버스 노선이 다음과 같이 있다고 하자.

 

[0, 4], [2, 6], [5, 0], [7, 9], [9, 4]

 

 


위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 

따라서 취소되는 버스 노선은 ①과 ④이다.

 

버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오.

 


입력형식

입력의 첫 번째 줄에는 버스 정류소의 개수 N ( 3 ≤ N ≤ 1,000,000,000 ) 이 주어지고

두 번째 줄에는 버스 노선의 수 M ( 2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1 부터 M 까지의 번호로 구분된다. 

그 다음 M 개의 줄에는 1 번 노선부터 순서대로 각 버스 노선 [a, b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다,

단, 0≤ a, b ≤ N-1 이고 a ≠ b 이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 

또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다. 

 

<제약조건>

• 부분문제 1: 전체 점수 100점 중 13점에 해당하며, M ≤ 5,000 이고, 입력으로 주어지는 모든 버스 노선 [a, b]에 대해 a 〈 b 이다. 

• 부분문제 2: 전체 점수 100점 중 28점에 해당하며, M ≤ 5,000 이다. 

• 부분문제 3: 전체 점수 100점 중 16점에 해당하며, 입력으로 주어지는 모든 버스 노선 [a, b]에 대해 a 〈 b 이다. 

• 부분문제 4: 전체 점수 100점 중 43점에 해당하며, 원래의 제약조건 이외의 아무 제약 조건이 없다.


출력형식

입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다.

입력 예

10
5
0 4
2 6
5 0
7 9
9 4

출력 예

2 3 5

입력 예

20
4
14 17
18 3
8 6
9 13

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP