P16136 [ICPC 2018 NAIPC] Winter Festival

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$。

翻译由 DeepSeek V3.2 完成