Tourist Reform

题意翻译

Berland是一个旅游国家!至少——Berland政府对此充满信心。 Berland有 $n$ 个城市,其中一些城市以两条道路连接。每条路连接两个不同的城市。在Berland没有连接同一城市的道路。城市之间两两可达。 根据改革,每一条道路将成为单向的。它将面向两个方向之一。 为了最大限度地提高Berland的旅游吸引力,在对每个城市进行改革后,我将计算值 $R_i$ 。它将等于城市 $X$ 的数量,其中有一个从城市 $i$ 到城市 $X$ 的有向路径。换言之,$R_i$ 等于可以通过道路从 $i$ 到达的城市的数量。 政府确信游客的注意力将集中在 $R_i$ 的最小值上。 帮助Berland政府进行改革,以最大限度地提高 $R_i$ 的最小值。 翻译提供者:jzzcjb

题目描述

Berland is a tourist country! At least, it can become such — the government of Berland is confident about this. There are $ n $ cities in Berland, some pairs of which are connected by two-ways roads. Each road connects two different cities. In Berland there are no roads which connect the same pair of cities. It is possible to get from any city to any other city using given two-ways roads. According to the reform each road will become one-way. It will be oriented to one of two directions. To maximize the tourist attraction of Berland, after the reform for each city $ i $ the value $ r_{i} $ will be calculated. It will equal to the number of cities $ x $ for which there is an oriented path from the city $ i $ to the city $ x $ . In other words, $ r_{i} $ will equal the number of cities which can be reached from the city $ i $ by roads. The government is sure that tourist's attention will be focused on the minimum value of $ r_{i} $ . Help the government of Berland make the reform to maximize the minimum of $ r_{i} $ .

输入输出格式

输入格式


The first line contains two integers $ n,m $ ( $ 2<=n<=400000,1<=m<=400000 $ ) — the number of cities and the number of roads. The next $ m $ lines describe roads in Berland: the $ j $ -th of them contains two integers $ u_{j} $ and $ v_{j} $ ( $ 1<=u_{j},v_{j}<=n $ , $ u_{j}≠v_{j} $ ), where $ u_{j} $ and $ v_{j} $ are the numbers of cities which are connected by the $ j $ -th road. The cities are numbered from $ 1 $ to $ n $ . It is guaranteed that it is possible to get from any city to any other by following two-ways roads. In Berland there are no roads which connect the same pair of cities.

输出格式


In the first line print single integer — the maximum possible value $ min_{1<=i<=n}{r_{i}} $ after the orientation of roads. The next $ m $ lines must contain the description of roads after the orientation: the $ j $ -th of them must contain two integers $ u_{j},v_{j} $ , it means that the $ j $ -th road will be directed from the city $ u_{j} $ to the city $ v_{j} $ . Print roads in the same order as they are given in the input data.

输入输出样例

输入样例 #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