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 P₁ = A, P₂, ..., P_k = B, such that P₁ is P₂'s boss, P₂ is P₃'s boss, ..., and P_k-1 is P_k'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 M_min, which is the minimum number of "boss" relations that the company has to keep. In the next M_min 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