Busiest interchange: hints, no solution

A city transit map has n stations numbered from 0 to n - 1. Each row of links is one line segment joining two different stations. Two segments may join the same pair of stations, and each of them counts on its own. The interchange count of a station is the number of segments that touch it.

Return the station with the highest interchange count. If several stations share the highest count, return the smallest id among them. If there are no segments at all, every station has count zero, so return 0.

Examples

Input

n = 4, links = [[0, 1], [1, 2], [1, 3]]

Output

1

Note

Station 1 touches three segments and no other station touches more than one.

Input

n = 5, links = [[0, 1], [2, 3], [3, 4], [2, 4]]

Output

2

Note

Stations 2, 3 and 4 each touch two segments; the smallest id among them is 2.

Input

n = 3, links = []

Output

0

Note

With no segments every count is zero, so the smallest id, 0, is returned.

Constraints

• 1 <= n <= 100000
• 0 <= links.length <= 100000
• Every link joins two different stations in the range 0 to n - 1

Hint 1: a nudge

What single number could you attach to each station to say how busy it is, and how many segments would you have to look at to fill that in for all stations at once?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing