Word Equalizing

Time limit1sMemory limit128 MB

Summary

Append the given words to x and y any number of times to make them equal, and output the minimum total number of appends, or NIE if impossible.

Level: Medium7 of 10
Topics: String, Graph, BFS, String matching
Solved: No attempts yet

Problem

You are given two words $x$ and $y$ , together with a series of $k$ words $(w_1, w_2, \ldots, w_k)$ . The operation $w \oplus w_i$ appends the series word $w_i$ ( $1 \le i \le k$ ) to the end of the word $w$ (concatenation): it writes $w_i$ immediately after $w$ .

By appending series words to the ends of $x$ and $y$ (using any word as many times as you like, on either word), decide whether the two words can be made identical. If it is possible, output the minimum number of $\oplus$ operations required; otherwise output NIE ("no" in Polish).

For example, the words abba and ab can be equalized using the series baaabad, aa, badccaa, cc: append aa and badccaa to abba, and append baaabad, then cc, then aa to ab. Both become abbaaabadccaa, using $2 + 3 = 5$ operations in total.

Input

The first line contains a positive integer $k$ ( $1 \le k \le 40$ ), the length of the series. The second and third lines contain the descriptions of $x$ and $y$ . The next $k$ lines contain the descriptions of $w_1, w_2, \ldots, w_k$ , one per line. Each description consists of the word's length (a natural number) and the word itself, separated by a single space. Every word consists only of lowercase letters a to z and has length at most 2,000. The total length of all given words is at most 5,000.

Output

If $x$ and $y$ can be equalized, output the minimum number of $\oplus$ operations (a nonnegative integer). Otherwise, output NIE.

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa
```
Expected output
```
NIE
```