Mother Vertex

hard

Graphs

Question Solve Solutions

Given a Directed Graph, find a Mother Vertex in the Graph (if present). 
A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.

Input Format

First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.

Output Format

Print the mother vertex if present else print -1.

Constraints

1&lt;= N &lt;= 10000
1&lt;= M &lt;= (N*(N-1))/2
1&lt;= ai, bi &lt;= N

Example

Input

Output

Kosaraju Algorithm

Minimum Cost To Connect All Cities

Related Questions

easy Sentence Similarity easy Redundant Connection easy Alien Dictionary medium Bellman Ford hard Negative Weight Cycle Detection medium Pepcoder And Reversing medium Pepcoding Course Schedule hard Kosaraju Algorithm medium Minimum Cost To Connect All Cities medium Number Of Enclaves medium Zero One Matrix medium Number Of Distinct Island easy Rotting Oranges medium As Far From Land As Possible easy Shortest Bridge hard Articulation Point