Description

你拥有某个地区的航线地图。该地区的所有机场以及它们之间的所有直飞航线都标记在地图上。这里，直飞航线是指提供双向直飞航班的航线。

以伟大的数学家莱昂哈德·欧拉命名的欧拉环游是一种行程，它访问该地区的所有机场，并搭乘该地区可用的每条直飞航线恰好一次。准确地说，它是一个机场列表，满足以下所有条件。

• 列表以同一个机场开始和结束。
• 列表中相邻的机场对之间存在直飞航线。
• 该地区的所有机场至少在列表中出现一次。注意，允许某些机场出现多次。
• 对于所有存在直飞航线的机场对，该对机场（无论顺序）在列表中应恰好出现一次作为相邻项。

仅凭地图上列出的直飞航线，可能并不总是能找到欧拉环游。然而，添加更多航线可能使得欧拉环游成为可能。你的任务是找出一组额外的航线，使得欧拉环游成为可能。

Input Format

输入包含单个测试用例。

$$\begin{aligned} & n \quad m \\ & a_1 \quad b_1 \\ & \vdots \\ & a_m \quad b_m \end{aligned}$$

$n$ （$3 \leq n \leq 100$）是机场的数量。机场编号从 $1$ 到 $n$。$m$ （$0 \leq m \leq \frac{n(n-1)}{2}$）是存在直飞航线的机场对的数量。接下来的 $m$ 行中，第 $i$ 行（$1 \leq i \leq m$）的整数 $a_i$ 和 $b_i$ 表示在两个机场之间有直飞航线运营。你可以假设 $1 \leq a_i < b_i \leq n$，并且对于任意 $i \neq j$，满足 $a_i \neq a_j$ 或 $b_i \neq b_j$。

Output Format

输出一组能使得欧拉环游成为可能的额外直飞航线。如果有两种或更多种不同的可行集合，输出其中任意一种均可。输出应采用以下格式。

$$\begin{aligned} & k \\ & c_1 \quad d_1 \\ & \vdots \\ & c_k \quad d_k \end{aligned}$$

$k$ 是要添加的直飞航线数量，可能为零。接下来的 $k$ 行中，每行应包含一对用空格分隔的整数。第 $i$ 行（$c_i < d_i$）的整数 $c_i$ 和 $d_i$ 表示要在它们之间添加一条直飞航线的机场编号。这些对，即对于 $1 \leq i \leq k$ 的 $(c_i, d_i)$，应互不相同且不应出现在输入中。

如果添加新的直飞航线永远无法使得欧拉环游成为可能，则在一行中输出 -1。

4 2
1 2
3 4

2
1 4
2 3

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

-1

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

3
1 5
2 4
2 5

4 3
2 3
2 4
3 4

-1

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

0