Skills101
← All coding problems

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 m lines: a b (a follows b)

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).

Loading editor…

Log in to run and submit your code — it's free.