Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB
统计

【题目描述】
嘉然给你两个点数、边数相同的有标号无向简单图 G, H,问你能不能在 2022306 次如下操作内 将 G 变成 H,如果可以请给出方案:
选择四个不同的点 a, b, c, d,其中存在边 (a, b),(c, d) 不存在边 (a, c),(b, d),将其调整为不存在边 (a, b),(c, d) 存在边 (a, c),(b, d)。
【输入格式】
从文件 graph.in 中读入数据。
第一行两个数 n, m。表示两张图的点数、边数。
接下来 m 行描述 G 的边 (u, v)。
接下来 m 行描述 H 的边 (u, v)。
【输出格式】
输出到文件 graph.out 中。
如果 G 无法变成 H,请输出 −1。
否则输出一个数 c,表示操作次数,需要满足 c ≤ 2022306。
接下来 c 行每行四个数 a, b, c, d,表示一次操作。
【样例输入】

4 2
1 2
3 4
1 3
2 4
【样例输出】

1
1 2 3 4
【数据范围与提示】
对于 20% 的数据满足 n ≤ 6。
对于 50% 的数据满足 n ≤ 100。
对于 100% 的数据满足 n ≤ 2000。保证图没有重边自环。