Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

COMPANY - Company

In Plumsoft company, there is a hierarchy among employees, i.e. some of them are bosses to the others. Person A is in charge of person B if there is a sequence of employees P1 = A, P2, ..., Pk = B, such that P1 is P2's boss, P2 is P3's boss, ..., and Pk-1 is Pk's boss. As Plumsoft is a pretty sane company, you can assume that no two employees can be in charge of each other. The management wants to cut the costs of meetings (they eat a lot of food), so they plan to minimize the number of "A is boss of B" relations by keeping only some of the existing ones. However they want to keep all "A is in charge of B" relations. Please, help them to successfully make this transition.

Input

The first line of the input contains two integers N and M separated by a space character (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000). N is the number of employees, and M is the number of "boss" relations in the company. Employees are labeled with numbers 1 through N. Each of the next M lines contain two labels A and B separated by a space character, meaning that A is a boss of B.

Output

In the first line of the output, write a single number Mmin, which is the minimum number of "boss" relations that the company has to keep. In the next Mmin lines write the relations that are kept. In each line, write two labels A and B separated by a space character, meaning that A is still a boss of B. If there are multiple solutions, write any of them. Relations can be listed in any order. Each line of the output should be followed by a newline.

Example

Input:
5 8
3 5
1 4
4 3
1 3
4 5
1 2
1 5
2 3

Output:
5
3 5
1 4
4 3
1 2
2 3

Added by:Minilek
Date:2008-12-22
Time limit:0.233s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:MIT Individual Contest 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.