题目描述

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

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

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

• 对于任意一个区域，考虑与该区域相邻的任意两条不同的道路，设这两条道路上的装饰成本分别为 $a$ 和 $b$，必须满足 $(a + b) \bmod 3 \neq 1$。
• 任意一个环上所有道路装饰成本之和必须为奇数。

环是由道路连接形成回路的一系列区域，每个区域在环中恰好出现一次。

Peter 想知道：他能够按照要求装饰城市所需的最小总成本是多少？

输入格式

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

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a < b \leq n$），表示区域 $a$ 和 $b$ 之间有一条直接相连的道路。没有两条道路连接相同的两个区域。图中不一定所有区域之间都是连通的。

输出格式

输出一个整数，表示装饰城市所需的最小总成本。如果无法按照 Peter 的要求装饰城市，则输出 $-1$。

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

-1

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

5

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

5

提示

翻译由 DeepSeek V3.2 完成