Find the Influencer
easyGraphs II+10 XPTime limit 2s
In a small social app, n people are numbered 1 … n. A pair a b means a follows b. The influencer is the person who is followed by everyone else and follows nobody. Find the influencer — there is at most one.
Input:
- line 1:
n m - next
mlines:a b(afollowsb)
Output: the influencer's number, or -1 if there is none. (With n = 1, that one person is the influencer.)
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, a ≠ b, no pair is repeated.
Think about it: count, for every person, how many people they follow (out-degree) and how many follow them (in-degree). The influencer has in-degree n − 1 and out-degree 0. One pass over the pairs is enough.
Sample input 1
3 2 1 3 2 3
Sample output 1
3
Sample input 2
3 3 1 3 2 3 3 1
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).