Pepcoder And Reversing

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai and bi where ai and bi represents an edge from a vertex ai to a vertex bi.

You have to find the minimum number of edges you have to reverse in order to have atleast one path from vertex 1 to N, where the vertices are numbered from 1 to N.
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 minimum number of edges we need to revert. If there is no way of having at least one path from 1 to N, print -1.
Question Video
Constraints
1<= N <= 10^4
1<= M <= 10^6
1<= ai, bi <= N
Sample Input
7 7
1 2
3 2
3 4
7 4
6 2
5 6
7 5
Sample Output
2


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name