Pyramide maudite – Épreuve régionale 2015

Énoncé¶

Jadis, la pyramide de Quuxfootl était réputée maudite : les passants qui s'y égaraient se retrouvaient égarés dans des galeries semblant être mues par une force vitale, le chemin qu'ils avaient pris pour arriver se refermant derrière eux.

De récentes recherches archéologiques ont révélé le mécanisme employé par les prêtres pour effrayer les intrus : ils commandaient, par des interrupteurs, les tunnels du complexe pyramidal ; chaque interrupteur était relié à deux galeries, et selon sa position, l'une s'ouvrait alors que l'autre était fermée. (Les Mésoaméricains n'ayant pas connaissance du circuit va-et-vient malgré leurs connaissances sophistiquées en mécanique, deux interrupteurs n'étaient jamais reliés à un même tunnel.)

Le professeur Marchand a remarqué que quand les interrupteurs sont tous en position basse, deux chambres sont toujours reliées par un unique chemin simple empruntant les galeries ouvertes. Il se demande si cette propriété reste vraie quelle que soit la position des interrupteurs.

Pour répondre à sa question, il vous fournit un plan du complexe pyramidal (c'est un multigraphe : deux chambres peuvent être reliées par plusieurs tunnels) et, pour chaque interrupteur, une paire (a,b) où a est le tunnel ouvert lorsque l'interrupteur est en position basse (b étant alors fermé), et b est ouvert lorsque l'interrupteur est en position haute (a étant alors fermé). Les paires sont disjointes. Les tunnels qui ne sont commandés par aucun interrupteur sont tout le temps ouverts.

Entrée¶

L’entrée comprendra :

• sur la première ligne, 3 entiers séparés d’une espace : le nombre de chambres, de tunnels et d'interrupteurs, respectivement notés n_c, n_t et n_i
• sur chacune des n_t lignes suivantes, la description d'un tunnel : deux entiers séparés d'une espace donnent les numéros des chambres aux deux extrémités du tunnel
• sur chacune des n_c lignes suivantes, la description d'un interrupteur : les deux tunnels qu'il commande sont identifiés par leurs deux numéros séparés d'une espace

Les chambres sont numérotées de 0 à n_c - 1 ; les tunnels sont numérotés de 0 à n_t - 1 selon l'ordre dans lequel leurs descriptions sont fournies.

Sortie¶

Vous afficherez en sortie :

• 1 si la condition demandée est bien satisfaite par tous les multigraphes induits par sélection d'une arête sur deux dans chaque paire ;
• 0 sinon.