题目描述

一套多米诺骨牌由若干块 $2\times 1$ 的长方形牌组成。每块牌被一条平行于短边的线分成两个相等的半块。每个半块上画有若干点，点数在 $0$ 到 $M$ 之间，包括 $0$ 和 $M$。

完整的一套多米诺包含所有可能的不同无序数对。

例如，当 $M=3$ 时，完整套装包含 $10$ 块牌：

$$\{0,0\},\{0,1\},\{0,2\},\{0,3\},\{1,1\},\{1,2\},\{1,3\},\{2,2\},\{2,3\},\{3,3\}.$$

多米诺牌可以首尾相接形成若干条链。两块牌可以连接，当且仅当它们连接处相邻半块上的点数相同。

现在从完整套装中移除 $N$ 块牌，但不会把所有牌都移除。

你的任务是用剩余的牌构造若干条链，使得每块剩余的牌恰好属于一条链，并使链的数量最少。

请编写程序 domino，给定 $M$ 以及被移除的牌列表，求满足条件的最少链数，并输出一种构造方案。

输入格式

第一行输入两个整数 $M$ 和 $N$，其中：

• $M$ 表示半块牌上可能出现的最大点数；
• $N$ 表示被移除的牌数。

接下来 $N$ 行，第 $i$ 行输入两个整数 $A_i,B_i$，表示第 $i$ 块被移除的牌两半上的点数。

输出格式

第一行输出一个整数 $V$，表示找到的最少链数。

接下来输出 $V$ 行，每行表示一条链。

一条链用一个点数序列表示，序列中的每两个相邻数字对应链中的一块牌。每个数字都应在 $0$ 到 $M$ 之间。

每条序列必须以 -1 结束。

数字之间用一个空格分隔。

数据范围

$$0 \le M \le 1024.$$

题目保证不会移除完整套装中的所有牌。

样例

输入

3 5
0 2
1 1
1 2
1 3
3 3

输出

1
2 2 3 0 0 1 -1

样例解释

该输出对应的牌链为：

$$\{2,2\},\{2,3\},\{3,0\},\{0,0\},\{0,1\}.$$

这些正好是移除指定牌后剩下的所有牌，因此只需要一条链。