SPOJ Brasil

Com o grande número de imigrantes argentinos no Canadá, o governo canadense está criando novas rodovias para as regiões mais distantes e isoladas habitadas por argentinos. Foram feitas diversas licitações para descobrir quais empresas poderiam conduzir as obras de cada rodovia. Cada empresa divulgou os orçamentos para as rodovias que ela poderia construir.

Os canadenses são conhecidos pela intolerância à corrupção e querem a qualquer custo evitar que alguma empresa seja beneficiada acima das outras. Então decidiram que cada empresa pode ser contratada para fazer no máximo uma das rodovias. Dá para perceber que no Brasil as coisas funcionam da mesma forma. (Mas não vamos entrar neste mérito!)

Entre duas cidades apenas uma empresa pode ter sido escolhida para construir uma rodovia.

Sua tarefa é: Dado um conjunto de orçamentos para construção das rodovias que ligam as cidades decida se existe uma maneira de atribuir as construções para as empresas, atendendo a exigência do governo canadense, e que seja possível viajar de qualquer cidade para qualquer outra usando as rodovias construídas (O governo canadense quer a qualquer custo garantir que os argentinos se comuniquem!).

Entrada

A entrada é composta de diversas instâncias. A primeira linha de cada instância consiste em três inteiros n (1 <= n <= 100), m (1 <= 10000) e k (1 <= k <= 2n) que indicam o número de cidades, número de orçamentos e o número de empresas. As próximas m linhas contém três inteiros u (1 <= u <= n), v (1 <= v <= n) e c (1 <= c <= k) indicando que a empresa c pode construir uma rodovia que liga a cidade u à cidade v.

As instâncias são separadas por uma linha em branco.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima sim se existe uma atribuição de construções de rodovias que atenda as exigências descritas acima, caso contrário imprima nao.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
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

Saída
Instancia 1
sim

Instancia 2
nao