P10748 [SEERC 2020] Mistake

You have $k$ machines. Each machine stores the $n$ numbers $1 \sim n$ in an **unordered** way. When you start a machine, it prints the frontmost number among the numbers stored in that machine, and then deletes it. Fortunately, you know $m$ pairs $(a_i, b_i)$, meaning that in every machine’s storage, each stored $a_i$ is before $b_i$. You also know the output produced by starting machines one by one. For each printed number, determine a plan that specifies which machine it came from, and make sure that the number of occurrences of each number $= k$. There may be multiple feasible solutions; output any one to get accepted.

The first line contains three integers $n, k, m\ (1 \leq n, k \leq 5 \times 10^5, 0 \leq m \leq 2.5 \times 10^5, 1 \leq n \times k \leq 5 \times 10^5)$. Then follow $m$ lines, each containing two integers $a_i, b_i\ (1 \leq a_i, b_i \leq n)$, and it is guaranteed that there is no cycle. Then one line contains $n \times k$ numbers, representing the sequence printed by the machines when they are started in order.

Output one valid starting plan.

Translated by ChatGPT 5