MVSTARS - Movie stars

Folding

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.