Ce problème devait être la leçon d'histoire de Juan sur les IOI de 1997 en Afrique du Sud. Cependant, le reste du comité a censuré la leçon, et c'est donc l'énoncé suivant qui vous est parvenu :

Abraham est un explorateur courageux qui va là où aucun programmeur n'est encore allé. Lors de sa prochaine expédition, il prévoit d'étudier un labyrinthe très curieux. Il sait que ce labyrinthe est une grille $n \times n$ avec une flèche dans chaque case. Chaque flèche pointe dans l'une des quatre directions possibles : haut, bas, gauche ou droite. Si Abraham entre dans une case, il est obligé de suivre les flèches à partir de cette case. Chaque flèche déplace Abraham d'une case dans la direction qu'elle indique ; s'il atteint une flèche pointant vers l'extérieur du labyrinthe, il peut s'échapper.

Abraham ne connaît pas l'orientation des flèches du labyrinthe, mais il dispose d'autres informations. Sur sa carte du labyrinthe, certaines cases sont coloriées en noir et d'autres en blanc. Il pense que s'il part de n'importe quelle case noire, il ne pourra jamais s'échapper du labyrinthe, tandis que s'il part de n'importe quelle case blanche, il finira par s'échapper.

L'hypothèse d'Abraham peut être fausse : il existe des dispositions de cases noires et blanches pour lesquelles les conditions indiquées ne peuvent pas être satisfaites simultanément pour toutes les cases, quelle que soit l'orientation des flèches. L'image suivante en montre un exemple.

La carte représente un labyrinthe dans lequel les cases blanches peuvent satisfaire l'hypothèse d'Abraham. S'il part de l'une ou l'autre, les flèches représentées le conduisent hors du labyrinthe, mais il est impossible qu'il reste prisonnier en partant d'une case noire, quelle que soit l'orientation que nous donnons aux flèches non représentées.

Abraham vous demande de l'aider à déterminer si, pour une coloration donnée des cases de sa carte, il existe une disposition des flèches conforme à sa conviction pour chaque case de la grille, noire comme blanche.

Entrée

• La première ligne contient un entier positif $n$.
• Chacune des $n$ lignes suivantes contient $n$ caractères, chacun étant 0 ou 1. 0 désigne une case noire et 1 une case blanche. Ces $n$ lignes décrivent la grille.

Sortie

Affichez SI s'il est possible d'orienter les flèches de sorte qu'Abraham ne puisse jamais s'échapper en partant d'une case noire et finisse par s'échapper en partant d'une case blanche.

Affichez NO si cela est impossible.

Exemples

Entrée 1

3
001
001
111

Sortie 1

SI

Entrée 2

2
01
10

Sortie 2

NO

Remarque

Le premier exemple correspond à la coloration suivante (représentée à gauche), accompagnée d'une disposition possible des directions des flèches :

Le deuxième exemple a été mentionné dans l'histoire du problème comme un cas où les conditions demandées ne peuvent pas être satisfaites simultanément pour toutes les cases.

Contraintes

• $2 \le n \le 1000$.

Sous-tâches

• Sous-tâche 1 (10 points) : $n=2$.
• Sous-tâche 2 (25 points) : Il est garanti que les cases noires forment une région connexe et qu'au moins deux coins du labyrinthe sont noirs.
• Sous-tâche 3 (25 points) : Il est garanti que les cases blanches forment une région connexe et que strictement moins de $4n-4$ cases sont noires.
• Sous-tâche 4 (40 points) : Aucune contrainte supplémentaire.

Remarque

Un ensemble de cases forme une région connexe s'il existe, entre chaque paire de ses cases, un chemin qui ne traverse que des cases de cet ensemble, en se déplaçant entre des cases partageant un côté. En particulier, les cases noires forment une région connexe s'il existe un chemin constitué uniquement de cases noires entre chaque paire de cases noires. De même, les cases blanches forment une région connexe s'il existe un chemin constitué uniquement de cases blanches entre chaque paire de cases blanches.

Dans le premier exemple, les cases blanches comme les cases noires forment une région connexe.

Dans le deuxième exemple, les cases noires ne forment pas une région connexe, car tout chemin entre elles passe aussi par une case blanche.