Word Equalizing

Memory limit: 32 MB

There are given two words , and finite series of words . An operation means a connection (concatenation) of word with another word (), i.e. is writing a word just after the word .

We want to verify if the words and can be equalized with words from the given series. The question is whether it is possible to extend the words and with words from the series in order to produce two identical words.

Example

The words abba and ab can be equalized with the words from the series: baaabad aa badccaa cc. In this purpose to the word abba we should add: aa and badccaa, and to the word ab — firstly baaabad, then cc, and finally aa. In both cases we result in the same word: abbaaabadccaa.

Task

Write a program that:

• reads from the standard input a length of a given series of words, then descriptions of two words and as well as descriptions of the words from the series: ,
• verifies whether the words and can be equalized with the words from the given series; if it is possible it finds the minimal number of operations , which are necessary,
• write this number to the standard output.

Input

In the first line of the standard input there is written a positive integer , . This is the length of the series . In the second and the third line there are descriptions of the words and . In the following lines there are descriptions of the succeeding words in the series ) — each description in a separate line. A description of the word consists of a natural number, which is the length of the word, and a word itself written as a series of characters. The number and the word are separated by a single space. Each word consists only of small English letters from a to z and its length is not greater than . The sum of lengths of all given words is not greater than .

Output

To the standard output there should be written:

• one nonnegative integer, the minimal number of operations , which are necessary to equalize given words and ,
• or the word NIE (which means “no” in Polish), if it is not possible to equalize the words.

Example

For the input data:

4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

the correct result is:

5

whereas for the input data:

4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

the correct output is:

NIE

Task author: Wojciech Rytter.