Livre piège – Regional event 2014

Level 4

Énoncé

Dans sa jeunesse, Joseph Marchand était un grand écrivain de livres « dont vous êtes le héros. » Ces livres ne se lisent pas de manière linéaire : à la fin de chaque chapitre, le lecteur à un choix à faire, les différentes réponses le menant à des chapitres différents. Ainsi on pourra trouver des : « Manger le chat ? - oui, aller au chapitre 12 - non, aller au chapitre 7 »

Dernièrement, un lecteur l'a contacté car il n'arrivait pas à la fin d'un de ses bouquins, il repassait sans cesse par le même chapitre. Vous expliquez à Joseph la terrible vérité : il est possible de ne jamais finir certains de ses livres.

Il vous demande d'écrire un programme pour vérifier si il est possible d'être piégé dans un de ses livres. Pour chaque chapitre, Joseph vous donne la liste des chapitres pouvant le suivre vous devrez renvoyer "1" si le lecteur peut être piégé et "0" s'il finit le livre quels que soient ses choix. La lecture commence au chapitre 0.

Entrée

  • Sur la première ligne, N, le nombre de chapitres.
  • Sur les N lignes suivantes : ki le nombre de réponses possibles à la fin du chapitre i, suivi (sur la même ligne) de ki entiers indiquant les chapitres suivants.
  • Un chapitre final est un chapitre sans choix possible, où ki = 0.

Sortie

Sur une ligne : "1" si le lecteur peut être piégé, "0" sinon.

Contraintes

1 <= N <= 10 000 0 <= ki <= 50

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
5
2 1 2
2 3 4
1 3
0
0
Sample output
0
Sample input
4
1 1
1 2
2 0 3
0
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.