ZOJ Problem Set - 2103
Marco Popo, the famous traveler, is traveling around the country of ACM. There are colored high-ways between cities (of course there is at most one high-way between any two cities), and his goal is to drive along each high-way once and only once. There is a strange rule to be followed when driving along: the color of one's tyres must match that of the high-way. As a result, he has to change tyres all the way he travels.
Given the total number of cities and the high-way map, you should decide at least how many times Popo needs to change tyres. Notice that Popo only changes tyres in cities, and he is allowed to start and end with tyres of arbitrary color.
There is a single blank line between test cases. A test case with 0 terminates the input, and this test case is not to be processed.
4 3 5
4 3 6
0 0 0
Author: SHI, Xiaohan
Source: Zhejiang University Local Contest 2004