There are given two words x, y and finite series of words (w₁, w₂, ..., w_k). An operation w ⊕w_i means a connection (concatenation) of word w with another word w_i (1 ≤ i ≤ k), i.e. is writing a word w_i just after the word w.</p>

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

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.

Write a program that:

• reads from the standard input a length k of a given series of words, then descriptions of two words x and y as well as descriptions of the words from the series: (w₁, w₂, ..., w_k),
• verifies whether the words x and y 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.

In the first line of the standard input there is written a positive integer k, k ≤ 40. This is the length of the series (w₁, w₂, ..., w_k). In the second and the third line there are descriptions of the words x and y. In the following k lines there are descriptions of the succeeding words in the series (w₁, w₂, ..., w_k)) — 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 2,000. The sum of lengths of all given words is not greater than 5,000.

출력 형식

To the standard output there should be written:

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

예제 입력 1

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

예제 출력 1

5

예제 입력 2

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

예제 출력 2

NIE