彼得最喜欢的季节是冬天。沉浸在节日气氛中的彼得想要装饰他的城市。

这座城市有许多区域，用于滑冰、滑雪和打雪仗等活动。有一些道路连接着某些区域对。彼得想在这些道路中的每一条上放置一种特殊的装饰。装饰有三种类型，成本分别为 0、1 和 2。

彼得希望他的装饰满足以下性质：

• 对于任何连接于同一区域的两条不同道路，设 $a$ 和 $b$ 为这两条道路上装饰的成本。必须满足 $(a + b) \pmod 3 = 1$。
• 任何环路上的装饰成本之和必须是一个奇数。

环路是指由道路连接形成闭合回路的区域序列。环路中的每个区域最多出现一次。

彼得想知道：他装饰城市所需支付的最低成本是多少？

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，其中 $n$ 是区域的数量，$m$ 是道路的数量。区域编号为 $1 \dots n$。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示有一条道路直接连接区域 $a$ 和 $b$。没有两条道路连接同一对区域。通过这些道路，可能无法从每个区域到达其他所有区域。

输出格式

输出一个整数，表示装饰城市的最低成本；如果无法按照彼得的要求装饰城市，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

-1

样例输入 2

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

样例输出 2

5

样例输入 3

10 10
5 8
2 6
3 9
1 4
9 10
4 6
5 9
7 8
7 10
2 3

样例输出 3

5