题目描述

城市 X 中有 N 个广场和 M 条街道。广场编号为 1 到 N。每条街道直接连接两个广场。任意两个广场之间最多只有一条直接街道。所有街道都允许双向通行，并且从任意广场都可以驾车到达任意其他广场。

市长有一个伟大的梦想：恰好选出一条街道作为步行街，也就是禁止汽车通行；然后把其余所有街道都改成单向。同时，从任意广场出发仍然必须能够驾车到达任意其他广场。

如果这做不到，市长也愿意退而求其次：不设置步行街，但把所有街道都改成单向，同时仍保持整张图强连通。

如果连这一点也做不到，那就只能维持现状了，市长会把精力投入到城市的其他项目中。

请编写程序 streets，帮助市长判断他的梦想能实现到哪一步。

---

输入格式

第一行输入两个正整数 N 和 M，分别表示广场数和街道数。

接下来 M 行，每行输入两个正整数，表示这条街道连接的两个广场编号。

---

输出格式

结果输出到标准输出。

情况 0：完全无法实现

如果连“不设步行街、把所有街道改成单向并保持强连通”都做不到，则只输出一行：

0

情况 1：只能部分实现

如果可以把所有街道改成单向并保持强连通，但不能额外选出一条步行街，则：

• 第一行输出 1
• 接下来输出 M 行，每行两个正整数 u, v，表示某条街道被定向为 u -> v

情况 2：可以完全实现

如果可以选出一条步行街，并将其余 M-1 条街道定向，使图仍强连通，则：

• 第一行输出 2
• 第二行输出两个正整数，表示被设为步行街的那条边的两个端点（顺序任意）
• 接下来输出 M-1 行，每行两个正整数 u, v，表示其余街道的方向为 u -> v

在情况 1 或 2 中：

• 边的输出顺序无关紧要；
• 如果有多个解，可以输出任意一个。

---

限制

• 2 ≤ N ≤ 50000
• 1 ≤ M ≤ 100000

---

评分说明

测试按组评分，只有该组所有测试全部通过，才能拿到该组对应分数。

• 20% 的测试中：2 ≤ N ≤ 500，1 ≤ M ≤ 1000，三种情况 0/1/2 都可能出现；
• 另外 30% 的测试中：N, M 无额外限制，但答案只可能是 0 或 1；
• 剩余 50% 的测试中：无额外限制。

---

示例 1

输入

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

输出

0

---

示例 2

输入

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

输出

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

---

示例 3

输入

5 7
1 2
2 3
3 4
1 4
3 5
2 5
2 4

输出

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