Arbre mystère – Épreuve régionale 2017

É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$