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.

Problem hidden on 2011-09-10 13:23:26 by [Trichromatic] XilinX

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

hide comments
Sudharsansai: 2015-03-23 14:54:43

Normal DFS with Memoization will give AC easily :)

Noszály Csaba: 2011-09-11 11:21:23

@XilinX: hope that you'll heal this problem :)

Noszály Csaba: 2011-09-10 09:31:15

there is no wrong answer for this prob, lol.........

Last edit: 2011-09-10 09:32:02
Varun Kumar V: 2011-06-23 06:05:39

something is wrong with test cases, I printed edges first before printing total count in my first upload and it got Accepted...

contesting: 2011-05-25 00:32:09

There's probably some problem with the special judge for this problem, I've sent a wrong solution that's being AC.

For sample input my AC program answer:

1
1 5
1 2
2 3
3 5
1 4

Mukhamed BUVANOV: 2011-02-03 11:18:43

Which boss will be after boss "1"?! boss "2" or boss "4"?

Jialin Ouyang: 2009-11-23 09:53:02

I've got serveal WA on this problem, so I submitted my friend's AC program and even the official solution, but still get WA, what's wrong with the test cases?

Last edit: 2009-11-23 10:56:31

Added by:Minilek
Date:2008-12-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2008