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.|

IREVIR - Ir e vir

Numa certa cidade há N intersecções ligadas por ruas de mão única e ruas com mão dupla de direcão. É uma cidade moderna, de forma que muitas ruas atravessam túneis ou têm viadutos. Evidentemente é necessário que se possa viajar entre quaisquer duas intersecções, isto é, dadas duas intersecções V e W, deve ser possível viajar de V para W e de W para V.

Sua tarefa é escrever um programa que leia a descrição do sistema de tráfego de uma cidade e determine se o requisito de conexidade é satisfeito ou não.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros N e M, separados por um espaço em branco, indicando respectivamente o número de intersecções (2 ≤ N ≤ 2000) e o número de ruas (2 ≤ MN(N−1)/2). O caso de teste tem ainda mais M linhas, que contêm, cada uma, uma descrição de cada uma das M ruas. A descrição consiste de três inteiros V, W e P, separados por um espaço em branco, onde V e W são identificadores distintos de intersecções (1 ≤ V, WN , VW ) e P pode ser 1 ou 2; se P = 1 então a rua é de mão única, e vai de V para W; se P = 2 então a rua é de mão dupla, liga V e W. Não existe duas ruas ligando as mesmas intersecções.

O ultimo caso de teste é seguido por uma linha que contém apenas dois números zero separados por um espaço em branco.

Saída

Para cada caso de teste seu programa deve imprimir uma linha contendo um inteiro G, onde G é igual a 1 se o requisito de conexidade está satisfeito, ou G é igual a 0, caso contrário.

Exemplo

Entrada:
4 5
1 2 1
1 3 2
2 4 1
3 4 1
4 1 2
3 2
1 2 2
1 3 2
3 2
1 2 2
1 3 1
4 2
1 2 2
3 4 2
0

Saída:
1
1
0
0


Adicionado por:Wanderley Guimarăes
Data:2011-02-12
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2010

hide comments
2020-07-15 19:58:56
Muito big brain esse problema, gostei.
2019-04-17 15:30:36
Não entendi pq no terceiro caso de teste do exemplo, a saída é 0... Os 3 vértices não estão conectados?
2015-08-16 22:50:29
Quem for fazer em C, coloca o tamanho da matriz em 700. acima disso da erro e abaixo o site da limite de tempo excedido.
2014-06-26 15:53:40 Bruno Guilherme


Last edit: 2014-06-26 15:54:24
2012-03-09 00:10:18 Diego H. [IFTM Uberlândia]
Mais saidas
2011-10-01 19:50:02 Matheus Flauzino [UNIS-MG]
Faz isso năo JessÉ!!!
2011-10-01 19:48:56 Lucas Amaral Caetano [UNIS-MG]
Problema resolvido jessÉ!
2011-08-01 06:23:41 bla
uhauhauhauhauh
2011-05-28 14:25:12 Douglas Eric [Anhanguera-SO]
olha, querer a gente năo quer.
Mas, se vocę pedisse com educaçăo, talvez alguem ajudasse
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.