很快一年级学生将被录取为贝尔兰大学的学生。入会的组织者为这个假期制定了一个计划。他们认为,如果一年级的学生互相赠送一些小纪念品就好了。当他们向一年级学生表达这个想法时,他们发现了以下事实:
- 一些新生已经互相认识;
- 每个新生同意只向他们已经熟悉的人赠送纪念品;
- 每个新生都不想赠送太多的纪念品。
主办方已经写下了所有熟悉的一年级朋友,现在想为每个新生确定应该给谁送纪念品。他们认为,每一对熟悉的学生中,恰好有一个学生必须向另一个学生赠送纪念品。
一年级的学生已经决定将最不幸的人称为必须赠送最多纪念品的人。作为回报,组织者承诺,最不幸的人将不幸降到最低程度:当然,与其他学生相比,他们必须赠送最多数量的纪念品,但这个数量会尽可能少。
组织者很忙,他们要求你为每一对一年级的朋友确定谁应该向谁赠送纪念品。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 5000, 0 ≤ m ≤ min(5000, n·(n - 1) / 2)) —一年级学生的人数和互相认识的学生对的数量。学生编号从 1 到 n。
以下 m 行中的每一行都包含两个整数 xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi) - 每对中的学生。
保证每对在列表中只出现一次。还保证如果列表中有一对 (xi, yi),则不存在 (yi, xi) 对。
输出
在第一行打印一个整数——最不幸的学生必须展示的最小纪念品数量。
接下来应该是 m 行,每行包含两个整数——彼此熟悉的学生。两人中的第一个号码必须是将纪念品赠送给两人中第二个学生的学生。
可以按任意顺序打印对。如果有很多解决方案,请打印其中任何一个。
示例
输入 #1
5 4 2 1 1 3 2 3 2 5
输出 #1
1 1 2 2 3 3 1 5 2
输入 #2
4 3 1 2 1 3 1 4
输出 #2
1 1 4 2 1 3 1
输入 #3
4 6 1 2 4 1 4 2 3 2 4 3 1 3
输出 #3
2 1 3 2 1 2 4 3 2 4 1 4 3