Bajtysia and Bajteusz are famous travelers who have visited almost every corner of Bajtocja. This land consists of $n$ cities, numbered from $1$ to $n$, which are connected by a network of one-way roads. However, they have grown bored with traditional methods of travel – they have already been everywhere they can reach.

Recently, Bajtysia came into possession of an ancient magical artifact – the Road Register. It allows for the creation of new one-way roads between cities. There is a catch, however. The magic of the register is capricious and only allows creating a road between two cities if it is currently impossible to travel from the first city to the second using the existing network of roads (i.e., there is no sequence of roads leading from the first city to the second; it may be the case, however, that there is a sequence of roads leading from the second city to the first). An attempt to create a road between cities that are already connected will fail and destroy the register.

For Bajtysia and Bajteusz, this is a wonderful challenge! They immediately decided that they want to conjure as many new roads as possible.

Unfortunately, Bajtysia and Bajteusz are too busy planning their next expedition to solve this problem on their own. Help them plan which roads should be created one by one so that their total number is as large as possible.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 1500$, $0 \le m \le n(n-1)$), representing the number of cities and one-way roads in Bajtocja, respectively. The next $m$ lines contain the descriptions of the roads. The $i$-th of these lines (for $1 \le i \le m$) contains two integers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), indicating that there is a one-way road from city $a_i$ to city $b_i$. The described one-way roads do not repeat.

Output

In the first line of output, print a single non-negative integer $k$ representing the maximum number of one-way roads that can be created such that each subsequent road connects a pair of cities between which it is not currently possible to travel. The next $k$ lines should describe the roads that should be created in order. The $i$-th of these lines (for $1 \le i \le k$) should contain two integers $c_i, d_i$ representing the cities between which the $i$-th road should be created. At the moment of creating this road, it should not be possible to travel from city $c_i$ to city $d_i$ using the already existing roads (i.e., both the initial ones and those created earlier). If there are multiple possible solutions, print any one of them.

Examples

Input 1

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

Output 1

3
4 1
6 4
7 6

Input 2

3 0

Output 2

5
3 1
3 2
2 1
2 3
1 2

Note

Explanation of the example: In the first example, the initially existing network of roads is illustrated below.

It is not possible to travel from city 4 to city 1, so such a road can be added to obtain the network of roads illustrated below.

After adding roads from city 6 to city 4 and from city 7 to city 6, we obtain a network in which it is possible to travel between every pair of cities. No more edges can be added.

Sample tests: Tests 0a, 0b are the sample tests above. Additionally: 0c: $n = 50, m = 50, a_i = i$, while $b_i = i + 1$ for each $i \neq 25$ and $i \neq 50$, and $b_{25} = 1$ and $b_{50} = 26$. 0d: $n = 500, m = 0$.