The Postman

Every morning Byteasar the postman must travel through every street of his district to deliver the mail. All roads are one-way and connect the crossroads, which are numbered from $1$ to $n$. Any two crossroads are joined by at most two roads, one in each direction.

Byteasar starts and finishes every route at the post office, located at crossroad $1$. He used to choose his routes himself, but a new regulation now limits that freedom. He is assigned a collection of route fragments: several sequences of crossroad numbers. Byteasar must pick a route that

• travels along every street exactly once,
• contains each assigned sequence as a run of consecutive crossroads (that is, the sequence appears as consecutive entries $v_i, v_{i+1}, \dots$ of the route),
• starts and ends at crossroad $1$.

It may happen that no route satisfies all of these requirements (for instance, an assigned sequence may require a road that does not exist). Decide only whether such a route exists.

The first line contains two integers $n$ and $m$ ($2 \le n \le 50000$, $1 \le m \le 200000$), the number of crossroads and the number of roads.

Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), describing a one-way road from crossroad $a$ to crossroad $b$. Each ordered pair $(a, b)$ appears at most once.

The next line contains an integer $t$ ($0 \le t \le 10000$), the number of assigned sequences. Each of the next $t$ lines describes one sequence: an integer $k$ ($2 \le k \le 200000$) followed by $k$ crossroad numbers. The total length of all sequences does not exceed $1000000$.

Print a single line:

• TAK if a route satisfying all requirements exists,
• NIE if no such route exists.

(TAK and NIE mean "yes" and "no" in Polish.)