El graf de la FME (2) P25513
La Lisbeth Salander (la protagonista de la famosa trilogia Millennium) és una crack de les matemàtiques, i pert tant s’està plantejant entrar a la FME. Com que resulta que a ella li agraden tant els homes com les dones, i coneix el graf de la FME, té curiositat per saber si és possible que tots els embolics hagin estat entre persones de sexe diferent. Ajudeu-la!
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de persones n, seguit de la informació de cada persona: el nom, el nombre mi de relacions que ha tingut, i els mi noms de les persones corresponents. Assumiu que tots els noms són diferents, i que per a tot parell de noms x i y, si x apareix a la llista de y llavors x existeix i y apareix a la llista de x, i que x mai no apareix a la llista de x. Suposeu 2 ≤ n ≤ 104, i que el nombre total de relacions no passa de 2n.
Sortida
Per a cada cas, digueu si és possible que totes les relacions hagin estat entre persones de sexe diferent.
Input
6 Alex 2 Felix Ivan Enric 2 Ivan Felix Ferran 1 Lander Lander 1 Ferran Ivan 2 Alex Enric Felix 2 Enric Alex 4 a 0 d 2 b c b 2 d c c 2 d b
Output
yes no
- Author
- Ferran Alet i Ivan Geffner
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++