You are given a directed graph with n vertices and m edges. The vertices in the graph are numbered from 1 to n. What is the minimum number of edges you need to reverse in order to have at least one path from vertex 1 to vertex n.
First line contains two integers n and m(1≤n,m≤2⋅106) — the number of vertices and the number of edges. The i-th line of the next m lines contains two integers xi and yi(1≤xi,yi≤n), denoting that the i-th directed edge connects vertices from xi to yi.
Print the minimum number of edges we need to invert. If there is no way of having at least one path from 1 to n, print −1.