New Year's '19 P3 - Santa's Journey

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

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.


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

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

1 2
2 6
6 5
5 7


There are no comments at the moment.