给定两个无向图 $G$ 和 $H$。$G$ 和 $H$ 都有 $n$ 个顶点和 $m$ 条边，顶点编号从 $1$ 到 $n$。现在，你需要将图 $G$ 变换为图 $H$。你可以执行任意次数的以下操作：

• 首先选择四个不同的顶点 $a, b, c$ 和 $d$。你需要确保 $a \sim b$，$c \sim d$，同时 $a \not\sim c$，$b \not\sim d$。
• 删除 $a$ 和 $b$ 之间的边，以及 $c$ 和 $d$ 之间的边。添加 $a$ 和 $c$ 之间的边，以及 $b$ 和 $d$ 之间的边。

这里 $a \sim b$ 表示 $a$ 和 $b$ 之间存在一条边，$a \not\sim b$ 表示 $a$ 和 $b$ 之间不存在边。

注意，每次操作都可以选择不同的 $a, b, c, d$ 集合。请确定是否可以将图 $G$ 变换为图 $H$。如果可以，你还需要提供详细的操作步骤。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($4 \le n \le 1000, 0 \le m \le \binom{n}{2}$)，表示图 $G$ 和 $H$ 的顶点数和边数。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u \neq v \le n$)，表示图 $G$ 中存在一条连接 $u$ 和 $v$ 的边。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u \neq v \le n$)，表示图 $H$ 中存在一条连接 $u$ 和 $v$ 的边。

图 $G$ 和 $H$ 均不包含重边或自环。

输出格式

如果无法将 $G$ 变换为 $H$，输出 “-1”（不含引号）。

否则，首先在第一行输出一个整数 $r$ ($0 \le r \le 3 \times 10^6$)，表示你需要的操作次数。

接下来的 $r$ 行，每行输出四个整数 $a_i, b_i, c_i$ 和 $d_i$，表示第 $i$ 次操作选择的顶点 $a_i, b_i, c_i$ 和 $d_i$。注意 $a_i, b_i, c_i, d_i$ 必须互不相同。

样例

样例输入 1

4 2
1 2
3 4
1 3
2 4

样例输出 1

1
1 2 3 4