P14897 [ICPC 2018 Yokohama R] Eulerian Flight Tour

你拥有某个地区的航线地图。该地区的所有机场以及它们之间的所有**直飞航线**都标记在地图上。这里，直飞航线是指提供双向直飞航班的航线。 以伟大的数学家莱昂哈德·欧拉命名的**欧拉环游**是一种行程，它访问该地区的所有机场，并搭乘该地区可用的每条直飞航线恰好一次。准确地说，它是一个机场列表，满足以下所有条件。 - 列表以同一个机场开始和结束。 - 列表中相邻的机场对之间存在直飞航线。 - 该地区的所有机场至少在列表中出现一次。注意，允许某些机场出现多次。 - 对于所有存在直飞航线的机场对，该对机场（无论顺序）在列表中应恰好出现一次作为相邻项。 仅凭地图上列出的直飞航线，可能并不总是能找到欧拉环游。然而，添加更多航线可能使得欧拉环游成为可能。你的任务是找出一组额外的航线，使得欧拉环游成为可能。

输入包含单个测试用例。 $$ \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$。

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