TOWER

탁자 위에 1번부터 N번까지 번호가 매겨진 빈 플라스틱 컵들이 놓여 있으며, 컵은 서로 포개어 쌓을 수 있다.

a→b 형태의 이동이 순서대로 주어진다. 이동 a→b는 컵 a가 속한 더미 전체를 컵 b가 속한 더미 위에 올려, 두 더미를 하나로 합치는 것을 뜻한다. 만약 a와 b가 같거나, 컵 a와 b가 이미 같은 더미에 있다면 그 이동은 아무 일도 하지 않는다.

예를 들어 컵이 7개이고 이동이 1→3, 2→6, 3→6, 4→7, 4→2로 주어지면, 탁자 위 상태는 다음과 같이 변한다.

                                                                        4
                                                                        7
                                                    1         1         1
                                                    3         3         3
                    1             1     2           2         2 4       2
1 2 3 4 5 6 7 --> 2 3 4 5 6 7 --> 3 4 5 6 7 --> 4 5 6 7 --> 5 6 7 --> 5 6

이동은 반드시 주어진 순서대로 적용해야 한다.

첫 번째 이동보다 앞서 수행할 이동 하나, 즉 0번째 이동을 추가로 넣을 수 있다. 모든 이동을 적용한 뒤 가장 큰 더미에 속한 컵의 수가 최대가 되도록 0번째 이동을 선택하여라.

첫째 줄에 두 정수 N과 M이 주어진다. (2 ≤ N ≤ 10000, 0 ≤ M ≤ 100000) N은 탁자 위 컵의 수, M은 이동의 수이다.

다음 M개의 줄에는 각각 이동 a→b를 나타내는 두 정수 a와 b가 주어진다.

0번째 이동을 가장 좋게 선택한 뒤 주어진 모든 이동을 적용했을 때, 가장 큰 더미에 속할 수 있는 컵 수의 최댓값을 정수 하나로 출력한다.