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 .
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 .
Print the minimum number of edges we need to invert. If there is no way of having at least one path from to , print .