문제
국경을 따라 순환 도로를 건설한 국가가 있다.
이 순환 도로에는 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점에 해당하며, 원래의 제약조건 이외의 아무 제약 조건이 없다.
출력
예제1
10
5
04
26
50
79
94
235
예제2
20
4
1417
183
86
913
3