beecrowd | 2128

Demonstration of Honesty!

By XI Maratona de Programação IME-USP, 2007 BR Brazil

Timelimit: 1

With the large number of Argentine immigrants in Canada, the Canadian government is creating new roads to the most distant and isolated regions inhabited by Argentines. Several bids were made to find out which companies could lead the works of each road. Each company released estimates for roads they could build.

Canadians are known for intolerance against corruption and want to avoid at all costs any company being favored above the others. They decided that each company can be hired to do at most one of the roads. You can see that in Brazil things work the same way. (But let's not get into this merit!)

Between two cities only one company may have been chosen to build a road.

Your task is: Given a set of estimates for construction of roads linking the cities, decide whether there is a way to assign buildings to companies, meeting the requirement of the Canadian government, and being possible to travel from any city to any other using the roads built.

Input

The input consists of several instances. The first line of each instance consists in three integers n (1 ≤ n ≤ 100), m (1 ≤ 10000) and k (1 ≤ k ≤ 2n) that indicates the number of cities, number of estimates and the number of companies. The next m lines contains three integers u (1 ≤ un), v (1 ≤ vn) and c (1 ≤ ck) indicating that the company c can build a road that connects the city u to the city v.

The instances are separated by a blank line.

The input ends with end of file.

Output

For each instance, you must print an identifier Instancia k, where k is the number of the actual instance. In the next line print sim if exists an attribution of building of roads that meets the demands described above, otherwise print nao.

After each instance print a blank line.

Sample Input Sample Output

3 3 3
1 2 1
2 3 2
3 1 3


6 9 5
1 2 3
2 3 4
3 1 5
1 4 1
2 5 1
3 6 2
4 5 2
5 6 1
6 4 1

Instancia 1
sim

Instancia 2
nao