Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Tourist Reform

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBerland 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}.

Input

The first line contains two integers *n*, *m* (2 ≤ *n* ≤ 400 000, 1 ≤ *m* ≤ 400 000) — 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.

Output

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.

Example

Input

7 9

4 3

2 6

7 1

4 1

7 3

3 5

7 4

6 5

2 5

Output

4

4 3

6 2

7 1

1 4

3 7

5 3

7 4

5 6

2 5

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 20:04:22 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|