CF732F Tourist Reform

伯兰德是一个旅游国家！至少，伯兰德政府对此充满信心，相信它将成为旅游胜地。 伯兰德有 $n$ 个城市，其中一些城市两两之间通过双向道路连接。每条道路连接两个不同的城市。在伯兰德，每一对城市之间至多只会有一条道路相连。通过现有的双向道路，可以从任意一个城市到达其他任何城市。 根据改革计划，每条道路都将改为单向道路，方向任选其一。 为了最大化伯兰德的旅游吸引力，改革后将对每个城市 $i$ 计算一个值 $r_i$，表示存在一条有向路径能从城市 $i$ 到达的城市 $x$ 的数量。换句话说，$r_i$ 表示可以通过道路从城市 $i$ 出发能够到达的不同城市数。 政府认为游客将关注所有 $r_i$ 的最小值。 请你帮助伯兰德的政府确定如何安排道路的方向，使得所有 $r_i$ 的最小值最大。

第一行包含两个整数 $n,m$（$2 \leq n \leq 400000, 1 \leq m \leq 400000$），分别表示城市的数量和道路的数量。 接下来 $m$ 行，每行包含两个整数 $u_j$ 和 $v_j$（$1 \leq u_j,v_j \leq n, u_j \neq v_j$），表示第 $j$ 条道路连接城市 $u_j$ 和城市 $v_j$。 城市编号为 $1$ 到 $n$。保证任意两个城市之间都可以通过若干条双向道路互达。同时，任意两座城市之间最多只有一条道路。

第一行输出一个整数，表示在道路定向后最小的 $r_{i}$ 的最大可能值。 接下来的 $m$ 行，每行输出两个整数 $u_j, v_j$，表示第 $j$ 条道路被定向为从 $u_j$ 指向 $v_j$。道路的输出顺序需与输入顺序一致。

由 ChatGPT 5 翻译