MVSTARS - Movie stars
Description
You're hoping to be a news reporter one day and you're looking for a movie star to interview. Your friend has given you a method for determining if there is a celebrity in the room, and who it is.
He tells you that a person is a celebrity if everyone else in the room knows them, but they don't know anybody else in the room.
Determine whether there is a celebrity in the room, and who it is.
Input
The first line will contain two numbers, N (2 <= N <= 1,000), the number of people in the room, and E (0 <= E <= N*(N-1)), the number of relationships. People are numbers 0 to N-1.
The next E lines will be two space-separated numbers A and B, meaning that person A knows person B.
Output
Print the celibrity's number if there is one. If there is no celebrity, print -1.
Examples
Input | Input |
---|---|
4 6 1 2 0 2 0 3 2 3 2 0 1 3 |
4 6 1 2 0 2 0 3 2 3 1 3 3 1 |
Output | Output |
3 |
-1 |
Added by: | BYU Admin |
Date: | 2015-11-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |