Marco Popo the Traveler

Time Limit: 1 Second    Memory Limit: 32768 KB

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.

Input

There are several test cases. Each test case begins with a line containing the total number of cities N (0 < N <= 10), the total number of colors C (0 < C <= 6), and the total number of high-ways in the country H (0 < H <= 20). Then H lines follow, each has three integers a, b, and c (0 <= a, b < N, 0 <= c < C) separated with whitespaces. This denotes that there is a high-way between city a and city b with color c.

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.

Output

For each test case, print a line with the minimum number of times Popo has to change tyres, so that he can achieve his goal. Otherwise print a line containing "No" only.

Sample Input

4 3 5
0 1 0
1 2 1
2 3 0
3 0 1
0 2 2

4 3 6
0 1 0
1 2 1
2 3 0
3 0 1
0 2 2
1 3 2

0 0 0

Sample Output

4
No

Submit

Source: Zhejiang University Local Contest 2004