Pathword Quest

Dir wird ein n x n Gitter aus kleinbuchstabigen englischen Buchstaben gegeben. Deine Aufgabe besteht darin herauszufinden, ob es in diesem Gitter einen einfachen Pfad gibt, der in der richtigen Reihenfolge den String s bildet.

Die Buchstaben auf dem Pfad müssen beim Lesen der Reihe nach den String s ergeben.

Eingabe

Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 6), die die Größe des Gitters angibt.

Die nächsten n Zeilen enthalten jeweils n kleinbuchstabige englische Buchstaben, die die Buchstaben in den Zellen des Gitters repräsentieren.

Die letzte Zeile enthält den String s (1 ≤ |s| ≤ 15), bestehend aus kleinbuchstabigen englischen Buchstaben.

Ausgabe

Gib YES aus, wenn ein einfacher Pfad existiert, der in der richtigen Reihenfolge den String s bildet. Andernfalls gib NO aus.

Beispiele

Eingabe

Ausgabe

3
a b e
d c f
g h i
abc

YES

3
a b e
d c f
g h i
abce

NO

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue