Pathword Quest

Տրվում է n x n չափի ցանց, որը պարունակում է փոքրատառ անգլերեն տառեր։ Ձեր նպատակն է պարզել, արդյոք գոյություն ունի ցանցում պարզ երթուղի, որը հերթականությամբ կարող է կարդալ տրված s տողը։

Երթուղու ընթացքում հանդիպող տառերը պետք է ձևավորեն s տողը պատշաճ հերթականությամբ։

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤ 6), որը նշում է ցանցի չափը։

Հաջորդ n տողերից յուրաքանչյուրում գրված է n փոքրատառ անգլերեն տառ՝ ցանցի վանդակների բովանդակությունը։

Վերջին տողում տրված է s (1 ≤ |s| ≤ 15) տողը, որն igualmente կազմված է փոքրատառ անգլերեն տառերից։

Ելք

Եթե հնարավոր է գտնել պարզ երթուղի, որի տառերը հերթականությամբ տալիս են s տողը, տպեք YES։ Հակառակ դեպքում տպեք NO։

Օրինակներ

Մուտք

Ելք

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