#162EasyGraphs· Degree and Structure

Star Network Hub

A small office network is wired as a **star**: one central switch (the hub) is cabled directly to each of the other machines, and there are no other cables. The machines are numbered `1` to `n` and the cable list was exported in arbitrary order, each cable written as a pair of machine numbers in either order. Given the list of cables of a star network with `n` machines (so there are exactly `n - 1` cables), return the number of the hub. The input is guaranteed to describe a valid star with at least three machines, so exactly one machine has a cable to every other machine.

Input format

`cables`: an array of `n - 1` pairs `[u, v]`, each naming the two machines a cable connects.

Output format

An integer: the label of the hub machine.

Examples

Input: cables = [[1, 2], [2, 3], [4, 2]]

Output: 2

Machine 2 is cabled to 1, 3 and 4, so it is the hub.

Input: cables = [[1, 2], [5, 1], [1, 3], [1, 4]]

Output: 1

Machine 1 appears in every cable, so it is the hub.

Input: cables = [[7, 3], [3, 1], [2, 3], [3, 6], [5, 3], [4, 3]]

Output: 3

Machine 3 appears in all six cables.

Constraints

3 <= n <= 10^5 machines, so 2 <= cables.length <= 10^5 - 1
1 <= u, v <= n and u != v for every cable
The cables form a star graph.

Study first

Graphs and Traversal: BFS and DFS

#graph
#degree
#hash-table