You are an electrician working in Moonlight City. One night, the city council gave you a call and informed you that the lampposts in Moonlight Square are all out of order, so they need your help. Moonlight Square is divided into
Input
The first line consists of two integers,
Output
Output the index of the lamppost which, when repaired, will light up the largest number of zones in the Square. Ties are broken by choosing the lamppost with the numerically largest index.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
Sample Input
10 5
1 2
1 3
1 4
1 5
2 6
Sample Output
1
Comments