样例输入 1

6 9
1 4
4 6
6 3
3 1
1 2
3 2
4 5
6 5
2 5

样例输出 1

1

样例输入 2

6 11
1 2
2 3
3 6
6 5
5 4
4 1
2 5
1 5
2 4
2 6
3 5

样例输出 2

-1