Byteland 正在运行一种革命性的新型交通系统。该系统既不需要道路，也不需要复杂的机械装置，只需要巨大的弹射器。

该系统的工作方式如下：Byteland 有 $n$ 座城市。每座城市的市中心都有一台弹射器。想要旅行的人会被放入一个特殊的胶囊中，弹射器会将该胶囊发射到其他某座城市的中心。每台弹射器都有足够的动力将胶囊发射到任何其他城市，胶囊内可以容纳任意数量的乘客。唯一的问题是弹射器充电需要很长时间，因此每天只能使用一次。

乘客可能需要多次使用弹射器。例如，如果乘客想从城市 A 前往城市 B，他们可以先使用一台弹射器从 A 移动到 C，然后换乘另一台弹射器从 C 移动到 B。

今天有 $m$ 名乘客。第 $i$ 位乘客想从城市 $a_i$ 前往城市 $b_i$。你的任务是找到一种方法，在一天内将所有乘客送达目的地，并使用尽可能少的弹射器次数，或者指出这是不可能的。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 1000, 0 \le m \le 10^5$)，分别表示城市数量和乘客数量。接下来的 $m$ 行包含数对 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)。

输出格式

第一行输出一个整数 $k$ —— 你需要使用的最少弹射器次数。

在接下来的 $k$ 行中，按执行顺序输出每次弹射的描述。每行描述应包含两个整数 $c_i, d_i$，分别表示发射城市的索引和目标城市的索引。

注意，你不需要打印每次发射时应该放入哪些乘客，但你提供的计划必须确保每位乘客都能到达他们的目的地。

如果无法将所有乘客送达，请输出单个数字 $-1$。

样例

样例输入 1

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

样例输出 1

5
5 1
1 2
4 2
2 3
3 5

样例输入 2

3 6
1 2
1 3
2 1
2 3
3 1
3 2

样例输出 2

-1