Bouquets

Kasia loves arranging bouquets from wildflowers. Near her home there are two meadows where rare and beautiful flower species grow, and she is especially fond of both.

Each meadow is like a maze in tall grass. It has several quiet clearings connected by corridors through the vegetation, and some corridors cross little bridges between hillocks. Kasia has known these paths since childhood, and every corridor can be walked in exactly one direction.

Each corridor joins two clearings, and corridors meet only at clearings. One species of flower grows in each corridor; the same species may grow in several corridors, but no two corridors leaving the same clearing grow the same species. Every time Kasia walks through a corridor she picks one flower of that corridor's species and appends it to her bouquet. A corridor may lead back to the clearing it starts from, and several corridors may lead to the same clearing. Kasia starts at clearing $1$ with an empty bouquet, and she may finish her bouquet only once she is back at clearing $1$ (she may also keep walking). If she walks through the same corridor several times, she picks one flower on each pass.

The length of a bouquet is the number of flowers it contains. Two bouquets are different if they have different lengths, or if for some position $k$ (not exceeding the bouquet length) the $k$-th flower of one bouquet differs from the $k$-th flower of the other.

Kasia wants to make bouquets all summer long. Walking any route she likes through the clearings and corridors, she can build any bouquet spelled out by a closed walk that starts at clearing $1$ and returns to clearing $1$. She wonders whether the two meadows can build exactly the same set of bouquets, that is, whether there is a bouquet that can be gathered on one meadow but not on the other. Help her find out.

The first line contains one natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets follow one after another.

Each test set consists of the descriptions of two meadows, given in order. A meadow is described as follows.

The first line of the description contains the number $n$ of clearings on the meadow. Clearings are numbered from $1$ to $n$, and Kasia always starts at clearing $1$. The next $n$ lines describe the corridors leaving clearings $1, 2, \dots, n$, in that order. Each such line begins with the number $q$ of corridors leaving that clearing, followed by $q$ pairs $A_i\ C_i$, where $A_i$ is the number of the clearing the corridor leads to and $C_i$ is a lowercase English letter naming the flower species growing in that corridor. For a single clearing all $C_i$ are distinct. Flower species are named consistently across both meadows. Assume $1 \le n \le 500$.

For each test set, print TAK if both meadows can build exactly the same bouquets, or NIE otherwise. Print the answers for consecutive test sets on separate lines.

Note: on the first meadow of the first test set you can build, for example, the bouquet abbc (by visiting clearings $1, 2, 3, 4, 1$ in turn) or acacacac (by visiting $1, 2, 1, 2, 1, 2, 1, 2, 1$). In the second test set the two meadows do not offer exactly the same bouquets: on the first meadow, for instance, you cannot gather the bouquet acac, which can be gathered on the second meadow.