HCI '16 - Lamppost

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type

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 N zones, each of which contains a single lamppost. When you arrived in Moonlight Square, you realised that you only have one light bulb in your toolbox, and so you can only repair one lamp. The lampposts are numbered 1 to N and each lamppost can light up a certain number of zones around it. Decide which lamppost to repair so that the most number of zones will be lit.

Input

The first line consists of two integers, N and C. The next C lines contain two integers each, C1 and C2, indicating that C1 can be lit from C2 and vice versa.

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:

1N,C1000000

Subtask 1 [20%]

1N,C<1000

Subtask 2 [80%]

1000N,C1000000

Sample Input

Copy
10 5
1 2
1 3
1 4
1 5
2 6

Sample Output

Copy
1

Comments

There are no comments at the moment.