{"id":"e109fc3a-51a5-4c22-a71e-fdfaff8e2a61","name":"Pepcoder And Reversing","description":"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.\r\n\r\nYou 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.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"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.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n1&lt;= ai, bi &lt;= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint main(){\n int n,m;\n cin>>n>>m;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\npublic static void main(String[] args) throws NumberFormatException, IOException {\nBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\nString[] st = br.readLine().split(\" \");\nint n = Integer.parseInt(st[0]);\nint m = Integer.parseInt(st[1]);\n\n\n\n}\n\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7 7\r\n1 2 \r\n3 2\r\n3 4\r\n7 4\r\n6 2\r\n5 6\r\n7 5","sampleOutput":"2\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"f47eca91-4162-445b-a8b2-0875114e92af","name":"Pepcoder And Reversing","slug":"pepcoder-and-reversing","type":1}],"next":{"id":"2244edcc-89b7-4e54-81b1-5b032bfab027","name":"Pepcoding and Reversing MCQ","type":0,"slug":"pepcoding-and-reversing-mcq"},"prev":{"id":"8335fb2d-48ce-45ec-a24b-3558e6b060c0","name":"Pepcoding Course Schedule","type":3,"slug":"pepcoding-course-schedule"}}}

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.

{"id":"e109fc3a-51a5-4c22-a71e-fdfaff8e2a61","name":"Pepcoder And Reversing","description":"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.\r\n\r\nYou 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.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"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.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n1&lt;= ai, bi &lt;= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint main(){\n int n,m;\n cin>>n>>m;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\npublic static void main(String[] args) throws NumberFormatException, IOException {\nBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\nString[] st = br.readLine().split(\" \");\nint n = Integer.parseInt(st[0]);\nint m = Integer.parseInt(st[1]);\n\n\n\n}\n\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7 7\r\n1 2 \r\n3 2\r\n3 4\r\n7 4\r\n6 2\r\n5 6\r\n7 5","sampleOutput":"2\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"f47eca91-4162-445b-a8b2-0875114e92af","name":"Pepcoder And Reversing","slug":"pepcoder-and-reversing","type":1}],"next":{"id":"2244edcc-89b7-4e54-81b1-5b032bfab027","name":"Pepcoding and Reversing MCQ","type":0,"slug":"pepcoding-and-reversing-mcq"},"prev":{"id":"8335fb2d-48ce-45ec-a24b-3558e6b060c0","name":"Pepcoding Course Schedule","type":3,"slug":"pepcoding-course-schedule"}}}
plane

Editor


Loading...

Pepcoder And Reversing

easy

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.

Constraints

1<= N <= 10^4 1<= M <= 10^6 1<= ai, bi <= N

Format

Input

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

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.

Example

Sample Input

7 7 1 2 3 2 3 4 7 4 6 2 5 6 7 5

Sample Output

2

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode