贝尔兰是一个旅游国家!至少,可以变成这样——贝兰德政府对此是有信心的。
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