CPU

시간 제한2초메모리 제한128 MB

요약

각 정점이 최대 한 번 등장하는 현들을 중요도 순으로 줄 때, 같은 색끼리 교차하지 않도록 두 색으로 나눌 수 있는 가장 긴 앞부분의 길이를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

에이든은 표준 부품으로 회로 기판 위에 조립할 수 있는 저가형 프로세서를 설계하고 있습니다. 부품들은 연결선(배선)으로 서로 이어지며, 배선은 자유롭게 구부러질 수 있고 반드시 직선일 필요는 없지만, 어떤 부품이나 다른 배선과도 절대 교차해서는 안 됩니다.

기본 배치는 이미 끝났습니다. $N$ 개의 모든 부품은 하나의 닫힌 고리, 즉 메인 루프로 연결되어 있으며, 이 고리를 따라 $1$ 번부터 $N$ 번까지 연속된 순서로 놓여 있습니다. 프로세서의 속도를 높이기 위해 에이든은 이제 일부 부품 쌍 사이에 직접 연결선을 추가하려고 합니다. 각 부품은 최대 하나의 추가 연결선만 가질 수 있습니다.

그는 추가하고 싶은 모든 연결을 중요도가 높은 순서대로 적어 두었습니다. 이 목록에서 가장 중요한 $K$ 개의 연결, 즉 앞에서부터 $K$ 개를 채택하려 하며, 채택한 배선들을 어느 두 개도 서로 교차하지 않게 동시에 그릴 수 있는 한도 안에서 $K$ 를 최대로 하려고 합니다.

부품들이 고리 위에 놓여 있으므로, 각 추가 배선은 고리의 안쪽 또는 바깥쪽으로 지나가게 그릴 수 있습니다. 같은 쪽에 그린 두 배선은 그 끝점들이 고리를 따라 서로 번갈아 나타날 때에만 교차하며, 서로 다른 쪽에 그린 배선은 결코 교차하지 않습니다. 따라서 어떤 연결들의 집합을 교차 없이 그릴 수 있는 것은, 모든 연결을 안쪽 또는 바깥쪽에 배정하여 같은 쪽에 있는 두 연결의 끝점이 서로 엇갈리지 않게 만들 수 있을 때, 그리고 오직 그때뿐입니다.

고리의 크기와 중요도 순으로 정렬된 원하는 연결 목록이 주어질 때, 가능한 $K$ 의 최댓값을 구하세요.

입력

첫째 줄에 메인 루프에 있는 부품의 개수 $N$ ( $1 < N < 200000$ )이 주어집니다.

둘째 줄에 고려 중인 추가 연결의 개수 $M$ ( $1 < M < 50000$ )이 주어집니다.

다음 $M$ 개의 줄에는 각각 두 정수 $P$ 와 $Q$ ( $1 \le P, Q \le N$ , $P \ne Q$ )가 주어지며, 이는 부품 $P$ 와 $Q$ 를 잇고 싶다는 뜻입니다. 연결들은 중요도가 높은 순서대로 나열되어 있습니다. 어떤 연결도 한 부품을 자기 자신과 잇지 않으며, 메인 루프에서 이웃한 부품끼리 이을 수는 있고, 어떤 부품도 둘 이상의 연결에 등장하지 않습니다.

출력

가능한 $K$ 의 최댓값을 한 줄에 하나의 정수로 출력하세요.

예제3

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