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

View as PDF

Submit solution

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

Author:
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 (ai,bi) (where 1iM) where bi=ai+1 for 1iM1. The start of the path is a1 and the end of the path is bM.

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

2N106

1M106

1ai,biN for all 1iM

The ai and bi form a path.

a1bM

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 ai,bi, 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

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

Output for Sample Input 1

Copy
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

Copy
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

Copy
4
1 2
2 6
6 5
5 7

Comments

There are no comments at the moment.