14711471 SUSTech Online Judge
Problem 1471 --Road Construction

1471: Road Construction

Time Limit: 1 Sec  Memory Limit: 1024 MB
Submit: 1025  Solved: 237
[Submit][Status][Web Board]


Given n cities and m roads. Sinzo wants to build these m roads one by one to guarantee all cities are connected, i.e., each city can reach all other cities. Sinzo wants to know how much roads after she built that all the n cities are connected.


The first line contains 2 integers, n, m \((1\leq n, m \leq 10^5)\), indicating there are n cities and m roads to build.

The next m lines, each line contains 2 integers u, v \((1\leq u, v \leq n)\), indicating Sinzo wants to build a unidirectional road from u to v.

Note that: these m roads are built in order.


Please output the minimum roads to build. If Sinzo build all m roads, the n cities are not connected, then output -1.

Sample Input

4 5
1 2
2 3
3 4
1 3
4 1

Sample Output