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
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
The
Input Specification
The first line contains two space-separated integers
Output Specification
Output an acceptable path in the following format.
On the first line, output the length
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
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
Comments