Reverse the graph
Very easy
Execution time limit is 6 seconds
Runtime memory usage limit is 256 megabytes
You are given a directed graph with vertices and edges. The vertices in the graph are numbered from to . What is the minimum number of edges you need to reverse in order to have at least one path from vertex to vertex .
Input
First line contains two integers and — the number of vertices and the number of edges. The -th line of the next lines contains two integers and , denoting that the -th directed edge connects vertices from to .
Output
Print the minimum number of edges we need to invert. If there is no way of having at least one path from to , print .
Examples
Input #1
Answer #1
Submissions 3K
Acceptance rate 29%