Description

Every morning, a busy postman needs to traverse all the city’s streets to deliver mail. All roads in the city are one-way and connected by intersections. For any two intersections $u, v$, there are at most two streets directly between them: one $u \to v$ and one $v \to u$ (i.e., there are no two $u \to v$ streets). All intersections are numbered from $1$ to $n$.

At intersection $1$, the postman may start his trip or end his trip. For a long time, the postman could freely choose his route, but a new regulation has disrupted his plan: each postman has been given several sequences of intersections, and now his route must satisfy the following requirements:

• The route must start at intersection $1$ and end at intersection $1$.
• The route must traverse each street exactly once.
• Each prescribed sequence of intersections must appear contiguously in the route. For example: the sequence 1 2 1 appears in 1 2 1 3, but does not appear in 1 2 3 1 (not contiguous).

The postman asks you to determine whether there exists a route that satisfies the above conditions; if so, also provide one such route.

Input Format

The first line contains two integers $n, m$, the number of intersections and the number of streets.

The next $m$ lines each contain two integers $a, b$, indicating there is a street $a \to b$. It is guaranteed that identical streets are not repeated and there are no self-loops.

The next line contains an integer $t$, the number of prescribed intersection sequences.

The next $t$ lines each describe one prescribed sequence: the first integer is $k$, followed by $k$ integers giving the sequence.

Output Format

If there exists a route that satisfies the conditions, output TAK; otherwise, output NIE.

If the answer is TAK, then output the route in the following lines, one integer per line.

Suppose you output $m+1$ integers, where the $i$-th printed integer is $v_i$. Your output must satisfy the following conditions:

• $v_1 = v_{m+1} = 1$.
• For all $1 \leq i \leq m$, there exists a street from $v_i$ to $v_{i+1}$.
• Each street in the city is used exactly once.
• Each prescribed intersection sequence appears contiguously in the route.

6 10
1 5
1 3
4 1
6 4
3 6
3 4
4 3
5 6
6 2
2 1
4
3 1 5 6
3 3 4 3
4 4 3 6 4
3 5 6 2

TAK
1
3
4
3
6
4
1
5
6
2
1

Hint

Constraints: $2 \leq n \leq 5 \times 10^4$, $1 \leq m \leq 2 \times 10^5$, $1 \leq a, b \leq n$, $a \neq b$, $0 \leq t \leq 10^4$, $2 \leq k \leq 10^5$, $\sum k \leq 10^5$.

Translated by ChatGPT 5