投递问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一座10层高的建筑物,搬运工小李需要搬运一些相同的包裹来往于各楼层之间。小李可以不搬运任何包裹而上楼下楼,也可以在搬运某一包裹的途中停下来,将该包裹放在他所处的楼层,然后去做其他的事情。小李从一层开始工作,并且工作结束后他必须返回一层。

现在请你编写一个程序,求出小李完成工作所需的最少上楼层数m(下楼层数不计),并且输出其搬运路径。

Input

输入数据的第一行有一个正整数k(0 < k <= 50),表示搬运工所需搬运的包裹数。

接下来有k行,每行有两个整数(整数之间用一个空格分开)。第s(2<=s<=k+1)行的两个整数i,j(1<=i,j<=10),表示s-1号包裹需要从第i层搬运到第j层。

Output

输出数据的第一行是一个整数m,表示搬运工完成工作所需的最少上楼层数。

接下来输出搬运工的搬运路径,每行有3个整数x,y,z(每两个整数之间用一个空格分开)。x表示搬运z号包裹的出发楼层;y表示搬运z号包裹的终止楼层;z表示被搬运包裹的编号,若z为0,则表示搬运工没有搬运任何包裹而上楼下楼。

Sample Input

2
2 5
8 10

Sample Output

9
1 2 0
2 3 1
3 4 1
4 5 1
5 6 0
6 7 0
7 8 0
8 9 2
9 10 2
10 9 0
9 8 0
8 7 0
7 6 0
6 5 0
5 4 0
4 3 0
3 2 0
2 1 0

Hint

Source