Santa has finished his deliveries, and is on his way back to the North Pole! Unfortunately, his GPS promptly fails on him, meaning that he has to fall back on the directions given to him by his predecessors.

While his predecessors have given him a sequence of directions that will get him to the North Pole, he is in a hurry and wants to find the minimum-length subsequence of these directions that achieves this same objective.

Formally, there are ~N~ locations numbered from ~1~ to ~N~. A direction is a pair of distinct locations ~a~ and ~b~, indicating a movement from ~a~ to ~b~. In this context, a path is a sequence of ~M~ directions ~(a_i,b_i)~ (where ~1 \le i \le M~) where ~b_i=a_{i+1}~ for ~1 \le i \le M-1~. The start of the path is ~a_1~ and the end of the path is ~b_M~.

The answer must be a subsequence of the original path that is also a path with the same start and end locations. If there are multiple answers with minimum length, output any of them.

Note: This problem uses a generator and custom grader, so judging may be slow.

Constraints

~2 \le N \le 10^6~

~1 \le M \le 10^6~

~1 \le a_i, b_i \le N~ for all ~1 \le i \le M~

The ~a_i~ and ~b_i~ form a path.

~a_1 \ne b_M~

Input Specification

The first line contains two space-separated integers ~N~ and ~M~, the number of locations and the length of the path, respectively.

~M~ lines follow; the ~i~-th one contains two space-separated integers ~a_i, b_i~, representing the ~i~-th direction in the path.

Output Specification

Output an acceptable path in the following format. On the first line, output the length ~K~. On the following ~K~ lines, output two integers representing a direction in this path.

Sample Input 1

6 6
3 1
1 6
6 3
3 5
5 1
1 4

Output for Sample Input 1

2
3 1
1 4

Explanation for Output for Sample Input 1

The output path goes from location 3 to 4, and consists of a sequence of directions that is a subsequence of the original path. There is no such path of length 1 since the direction ~(3,4)~ never appears in the original sequence.

Sample Input 2

7 10
1 2
2 3
3 4
4 5
5 6
6 7
7 2
2 6
6 5
5 7

Output for Sample Input 2

4
1 2
2 6
6 5
5 7