P3443 [POI 2006] LIS-The Postman

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.

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.

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.

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