← 返回题目列表

Codeforces · 732/F

F. 旅游改革

中文机器翻译题面 查看原题

贝尔兰是一个旅游国家!至少,可以变成这样——贝兰德政府对此是有信心的。

Berland 有 n 个城市,其中一些城市由双向道路连接。每条道路连接两个不同的城市。在贝尔兰,没有道路连接同一对城市。可以使用给定的双向道路从任何城市前往任何其他城市。

根据改革,每条路都将变成单向。它将面向两个方向之一。

为了最大化贝尔兰的旅游吸引力,改革后每个城市i将计算ri值。它将等于有从城市 i 到城市 x 的定向路径的城市 x 的数量。换句话说,ri 将等于从城市 i 通过道路可以到达的城市数量。

政府确信游客的注意力将集中在ri的最小值上。

帮助 Berland 政府进行改革,以最大化 ri 的最小值。

输入

第一行包含两个整数 n, m (2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000) — 城市数量和道路数量。

接下来的 m 行描述了 Berland 的道路:其中第 j 行包含两个整数 uj 和 vj (1 ≤ uj, vj ≤ n, uj ≠ vj),其中 uj 和 vj 是第 j 条道路连接的城市数量。

城市编号为 1 到 n。保证可以通过双向道路从任何城市到达任何其他城市。在贝尔兰,没有道路连接同一对城市。

输出

在第一行中打印单个整数 - 道路方向后的最大可能值 min1 ≤ i ≤ n{ri}。

接下来的m行必须包含定向后的道路描述:其中第j行必须包含两个整数uj、vj,这意味着第j条道路将从城市uj定向到城市vj。按照输入数据中给出的相同顺序打印道路。

示例

输入 #1

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

输出 #1

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