가위 바위 보

$N$명의 사람이 모여 가위바위보를 해서 우승자를 가리려고 한다.

토너먼트 방식은 재미가 없다는 의견이고, 풀 리그 방식으로 모든 사람이 가위바위보를 하기에는 시간이 너무 오래 걸린다는 의견에 새로운 방식으로 다음과 같은 게임을 진행하기로 했다.

먼저 $N$명의 참여자는 $1$번에서 $N$번까지의 번호를 추첨을 통해 부여 받는다. 이 후 넓은 체육관에 $N$명이 모여서 우승자를 가리는 게임을 시작한다. 정해진 시간 동안 참여자들은 무작위로 가위바위보를 하고, 그 결과는 특별 장치를 통해 중앙 서버에 시간 순으로 $(a, b)$와 같이 자동 기록된다. $(a, b)$는 $a$와 $b$가 가위바위보를 해서 $a$가 이기고 $b$가 졌다는 것을 의미한다. 모든 가위바위보 결과는 동시에 일어나지 않았다고 가정하며, 같은 쌍의 두 참여자가 두 번 이상 가위바위보를 하지 않는다.

우승자는 중앙 서버에서의 다음과 같은 과정을 통해 정해진다.

• 최초에는 각 참여자가 $N$개의 서로 다른 그룹에 속해 있는 것으로 초기화된다.
• 시간 순으로 기록된 가위바위보 결과를 스캔하면서, 각 결과 $(a, b)$에 대해 $a$와 $b$가 서로 다른 그룹에 속했을 경우, $a$가 속한 그룹과 $b$가 속한 그룹을 합쳐 하나로 만든다.
• 가장 많은 수의 참여자가 속한 그룹을 우승 그룹이라고 한다. 우승 그룹은 유일하지 않고 여러 개가 나올 수도 있다.
• 각 우승 그룹 내에서 가위바위보를 이긴 횟수가 가장 많은 사람이 그 우승 그룹의 대표이다.
• 가위바위보를 이긴 횟수가 가장 많은 사람이 여럿일 경우에는, 그중에 진 횟수가 가장 적은 사람이 그 우승 그룹의 대표가 된다.
• 위의 경우에도 대표가 한 명으로 정해지지 않는 경우에는 번호가 가장 작은 사람이 대표가 된다.
• 각 우승그룹의 대표 중에서 번호가 가장 작은 사람이 우승자이다.

서버에 기록된 결과가 주어질 때 우승자의 번호를 출력하는 프로그램을 작성하시오.

입력 형식

첫 번째 줄에는 사람들의 수 $N$과 서버에 기록된 가위바위보 결과의 개수 $M$이 입력으로 주어진다 ($1 \le N, M \le 200\,000$)

이후 $M$개의 줄에 걸쳐 가위바위보 결과를 나타내는 두 정수 $a$와 $b$가 공백으로 구분되어 시간 순서대로 주어진다. 이는 $a$와 $b$가 가위바위보를 해서 $a$가 이기고 $b$가 졌다는 것을 의미한다. ($1 \le a, b \le N$; $a \ne b$)

출력 형식

위의 규칙을 적용했을 때 우승자의 번호를 출력하라.

예제

5 4
1 4
2 3
2 5
3 5

2

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설