G: Cheminement dans un programme d'étude

La direction d'un programme d'études de premier cycle en informatique désire faire des modifications à son programme. Une telle modification entraîne souvent que les pré-requis de certains cours sont modifiés. De tels changements de pré-requis peuvent alors avoir un impact sur le cheminement des étudiants, c'est-à-dire, sur l'ensemble des cours qu'ils peuvent et devraient suivre à chaque session.

La direction du programme d'informatique aimerait pouvoir déterminer, de façon automatique, si un cheminement donné respecte les divers pré-requis des cours. En plus des pré-requis, on aimerait aussi pouvoir spécifier, pour certains cours, la session exacte où le cours devrait être suivi, par exemple, spécifier qu'un cours de base devrait nécessairement être suivi dès la première session.

Entrée

Les informations fournies dans les données d'entrée (stdin) sont les suivantes :

Le nombre maximum de cours que peut avoir chaque session.
Le nombre total de cours.
Les lignes suivantes donnent ensuite les divers cours et les contraintes qui leur sont associées. Plus précisément, chaque ligne indique :

Le sigle du cours (pour simplifier, un nombre entier) ;
La session où le cours doit obligatoirement être suivi. Si le nombre indiqué est 0, alors le cours peut être suivi à n'importe quelle session, en autant que les pré-requis appropriés sont respectés.
Le nombre de cours, possiblement 0, qui sont pré-requis au cours.
La liste des pré-requis.

Le nombre de sessions du cheminement à vérifier.
Les lignes suivantes décrivent ensuite le cheminement lui-même, c'est-à-dire, chaque ligne indique la liste des cours qui devraient être suivis à cette session.

Vous pouvez supposer que les cours indiqués (tant pour les pré-requis que ceux indiqués dans le cheminement) sont tous des cours valides, donc font partie de la liste des cours décrits. Vous pouvez aussi supposer que les nombres sont tous séparés par un unique espace.

Sortie

Pour une description donnée de programme, plusieurs cheminements peuvent évidemment être possibles. Le programme que vous devez écrire doit simplement déterminer si le cheminement indiqué dans les données d'entrée satisfait les contraintes décrites. Pour ce faire, il suffit que le programme produise soit la réponse `` OUI'', soit ``NON'' (sur une unique ligne, terminée par une fin de ligne).

Exemple (1)

Exemple d'entrée

Les données indiquées plus bas présentent la spécification d'un ensemble de cours pour un programme contenant 14 cours -- les commentaires ne seront évidemment pas présents dans les données -- suivi d'un cheminement possible pour cet ensemble de cours s'étalant sur trois (3) sessions.

5                           ;; Nombre maximum de cours par session

14                          ;; Nombre total de cours

1110 1 0                    ;; Sigle Session NbPrerequis ListeDePrerequis

1130 1 0

1600 0 0

1105 0 0

2015 0 0

2170 0 1 1110

2110 0 1 1110

4680 0 1 1110

1163 0 0

1081 0 0

3172 0 2 2170 2110

3102 0 2 1130 2110

3140 0 2 1130 2110

3180 0 1 2110

3                           ;; Nombre de sessions

1110 1130 1600 1105 2015    ;; Les sessions decrivant le cheminement

2170 2110 4680 1163 1081

3172 3102 3140 3180

Exemple de sortie

OUI

Exemple (2)

Exemple d'entrée

1110 1 0

1130 1 0

2110 0 1 1110

1080 0 0

1110 1130 2110

Exemple de sortie

NON