Arbre mystère – Regional event 2017

Level 6

Énoncé

Dans la forêt il y a un arbre mystérieux. Il y a, sur le tronc de cet arbre, un mot. Joseph Marchand décide de noter ce mot car il sait qu'il n'arrivera pas à s'en souvenir. Il n'a sur lui qu'un crayon et des bouts de papiers ne pouvant pas contenir plus de trois lettres. Il recopie alors chaque $\textit{facteur}$ de longueur trois, c'est à dire chaque sous-suite de trois lettres consécutives, sur un des bouts de papier. Il les met dans son sac et rentre chez lui.

Une fois arrivé, il constate qu'il n'a plus le même nombre de bouts de papier, il a dû en égarer sur la route. Il se demande s'il ne peut pas quand même reconstruire un mot avec uniquement les bouts de papier restants : cela étant, chaque facteur de longueur 3 doit correspondre à exactement 1 bout de papier, et tous les bouts de papier doivent servir à la réalisation de ce mot.

Aidez Joseph en lui indiquant s'il est possible ou non de construire un mot avec les $N$ bouts de papier restants.

Entrée

L'entrée comprendra plusieurs lignes :

  • La première ligne contiendra un entier $N$, le nombre de bouts de papier.
  • Les $N$ lignes suivantes contiennent chacune un mot de longueur 3, dont les caractères sont des lettres latines minuscules.

Sortie

Vous afficherez "OUI" s'il est possible de construire un mot, et "NON" sinon

Contraintes

  • $1 \le N \le 1\ 000$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5
ega
gam
the
ame
heg
Sample output
OUI
Sample input
5
ega
gam
txe
ame
heg
Sample output
NON
Sample input
7
pop
abp
opo
opa
pab
pop
bpa
Sample output
OUI

Submit your solution

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