题目描述

小码哥向小码弟宣战了。

小码弟的领土有$n$个城市，由$m$条道路连接，小码哥将投放魔法生物军队占领小码弟的城市，与被占领的城市相连的所有道路均会被魔法封锁。

然而，小码哥的魔法军队并不团结，如果存在两支魔法军队占领相邻的两个城市（相邻指两个城市由一条道路直接连接），那么这两支魔法军队就会为了抢功起冲突，这是小码哥不想看到的。

小码哥想知道，最少需要投放多少支魔法军队，可以封锁小码弟领土中的所有道路，且魔法军队之间不产生冲突。

输入格式

第一行输入两个整数$n,m$。 接下来$m$行，每行输入两个整数$u,v$，表示一条连接城市$u,v$的道路。

输出格式

输出一行一个整数，如果存在合法的方案，输出最少投放的魔法军队个数，否则输出-1。

样例输入 #1

3 3
1 2
1 3
2 3

样例输出 #1

-1

说明/提示

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