Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HONESTID - Demonstração de Honestidade!

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

Adicionado por:Wanderley Guimarăes
Data:2007-08-28
Tempo limite:0.384s-1.906s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva para Maratona de Programação do IME - 2007

hide comments
2012-03-09 18:57:03 Lucas
Năo entendi o probrema
2011-12-22 16:02:15 jose henrique schwengber junior
É só aqui que os acentos ficam com um "?" no lugar? Fica bastante desgastante a leitura...
2011-12-22 16:02:10 jose henrique schwengber junior
É só aqui que os acentos ficam com um "?" no lugar? Fica bastante desgastante a leitura...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.