设 $G$ 为一个简单的无向图，其顶点集和边集分别记为 $V(G)$ 和 $E(G)$。$G$ 中的两条边如果共享一个公共顶点，则称它们是相邻的。类似地，如果两个顶点共享一条公共边，则称它们是相邻的，在这种情况下，该公共边连接这两个顶点；一条边和一个顶点如果共享该顶点，则称它们是关联的。$E(G)$ 的一个子集 $M$ 被称为 $G$ 的一个匹配，如果 $M$ 中的任意两条边都不相邻；如果 $G$ 的每个顶点都恰好与 $M$ 中的一条边关联，则称 $M$ 为完美匹配。因此，$G$ 的一个匹配 $M$ 是完美匹配，当且仅当 $|M| = \frac{n}{2}$。

在多项式时间内寻找最大匹配（即包含边数最多的匹配）的算法已经存在。此外，关于完美匹配的存在性，还有两个更值得关注的问题：

• 给定 $V(G)$ 的一个划分 $S$ 和 $T$，且 $|S| = |T| = \frac{n}{2}$，是否存在一个完美匹配，使得每条边都连接 $S$ 中的一个顶点和 $T$ 中的一个顶点？
• 对于 $V(G)$ 的每一个划分 $S$ 和 $T$，且 $|S| = |T| = \frac{n}{2}$，是否存在一个完美匹配，使得每条边都连接 $S$ 中的一个顶点和 $T$ 中的一个顶点？

根据著名的霍尔定理（Hall's Marriage Theorem），第一个问题可以通过在多项式时间内运行最大匹配算法来回答。

是否存在一种有效的算法来回答第二个问题？一个对第二个问题给出肯定回答的图被称为强可匹配的（strongly matchable）；也就是说，如果图 $G$ 对于 $V(G)$ 的每一个划分 $S$ 和 $T$（满足 $|S| = |T| = \frac{n}{2}$）都存在一个完美匹配，且该匹配中的每条边都连接 $S$ 中的一个顶点和 $T$ 中的一个顶点，则称 $G$ 是强可匹配的。例如，图 J.1 (a) 所示的图是强可匹配的，因为对于三个划分中的每一个，都存在一个完美匹配：对于 $S = \{1,2,3\}$ 和 $T = \{4,5,6\}$，$M = \{(1,4), (2,5), (3,6)\}$；对于 $S = \{1,2,4\}$ 和 $T = \{3,5,6\}$，$M = \{(1,3), (2,5), (6,4)\}$；对于 $S = \{1,2,6\}$ 和 $T = \{3,4,5\}$，$M = \{(1,3), (2,5), (6,4)\}$。然而，图 (b) 不是强可匹配的，因为对于 $S = \{1,2,4\}$ 和 $T = \{3,5,6\}$，不存在这样的完美匹配。你的任务是编写一个高效的程序，用于判定一个具有偶数个顶点的图是否是强可匹配的。

输入格式

程序从标准输入读取数据。第一行包含两个正整数 $n$ 和 $m$，分别表示输入图的顶点数和边数，其中 $n$ 为偶数，$n \le 100$，且 $m \le \frac{n(n-1)}{2}$。接下来的 $m$ 行，每行包含两个正整数 $u$ 和 $v$，表示图中的一条边，连接顶点 $u$ 和 $v$。假设顶点编号从 $1$ 到 $n$。

图 J.1：(a) 中的图是强可匹配的，但 (b) 中的图不是。

输出格式

程序将结果输出到标准输出。在一行中打印一个整数。如果输入图是强可匹配的，则输出 $1$；否则，输出 $-1$。

样例

样例输入 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