3rd Balkan Olympiad in Informatics
Varna, Bulgaria, 5-11 October 1995

Day 2 - Problem 1 (Deliveries)



A firm occupies a 10-floors building. After finishing the work day, clerk John has to carry identical packages between floors. He starts and ends this job on floor 1 and can carry only one package.

Write a program that finds the minimum number m of the climbed floors and with the corresponding way of traveling.

Input:
The required deliveries are in the text file INPUT.TXT as follows:
First line: number of deliveries k<=50
Next lines: 2 numbers that determine a delivery, i.e. the floor sending and the floor receiving a package.
For example: 7

1 10

3 2

4 3

6 7

8 9

3 4

4 3



Output:
The deliveries are numbered in order they appear in the file: 1,2,...,k. Output is in the file in the following format:

First line: number m
Next lines: description of John's movements, which are described by triples: bi, ei, di, where,
bi - number of sending floor
ei - number of receiving floor
di - number of delivery, which package John has to carry from floor bi to floor ei. Number 0 (zero) means that John carries no package at this step.


Here is one possible answer for the given example. The output OUTPUT.TXT consists of:
12
1,6,1
6,7,4
7,6,0
6,10,1
10,8,0
8,9,5
9,4,0
4,3,4
3,4,6
4,3,7
3,2,2
2,1,0