题目描述

给定$n$个点，以及$m$个连接操作，操作按输入顺序进行，一次连接操作为$u,v$，会连接$u,v$两个点，连接具有传递性，即如果$a,b$连接，$b,c$连接，则$a,c$也认为被连接。

我们称任意一个点都和任意其他点之间连接的状态为连通。

请求出最早在第几次连接操作后达到连通状态，或者回答在所有操作结束后仍然无法连通。

输入格式

第一行输入两个整数$n,m$； 接下来$m$行，每行输入两个整数$u,v$。

输出格式

如果可以连通，输出最早在第几次操作后连通；否则输出-1。

样例输入 #1

4 4
1 2
1 3
2 4
1 4

样例输出 #1

3

说明/提示

有$1\leq n\leq 10^3,1\leq m\leq 10^5$。