8109번 - Word Equalizing 다국어

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.

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.