CPU

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

기본 배치는 이미 끝났습니다. $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$의 최댓값을 한 줄에 하나의 정수로 출력하세요.