P7965 [COCI 2021/2022 #2] Kutije

Matrin has toys in $n$ boxes. The boxes are numbered $1,2,3,\cdots,n$. Initially, each box contains one toy whose number is the same as the box number. Matrin invites $m$ friends to his home to play with the toys. He notices that after each friend finishes playing, they will put the toy that was originally in box $i$ into box $p_i$. You are given $q$ queries. For each query, you may invite friends in any order, and each friend may be invited any number of times. Determine whether there exists a plan such that toy $a$ ends up being placed into box $b$.

The first line contains three positive integers $n,m,q$, representing the number of boxes / toys, the number of friends, and the number of queries. The next $m$ lines each contain $n$ integers $p_i$. The testdata guarantees that $p_i$ is a permutation of $1 \sim n$. The next $q$ lines each contain two integers $a,b$.

Output $q$ lines. Each line should contain a string $\texttt{DA}$ (yes) or $\texttt{NE}$ (no).

**[Sample 1 Explanation]** - Query $1$: Initially, toy $1$ is already in box $1$, so output $\texttt{DA}$. - Query $2$: For the second query, there is no plan that satisfies the requirement, so output $\texttt{NE}$. - Query $3$: It is enough to invite friend $1$, so output $\texttt{DA}$. **[Constraints and Notes]** **This problem uses bundled subtasks.** - Subtask 1 (15 pts): $m=1$. - Subtask 2 (10 pts): $1 \le n,m,q \le 100$. For each query, if the answer is $\texttt{DA}$, it is guaranteed that there exists a plan that invites at most $2$ friends. - Subtask 3 (10 pts): $1 \le n,m,q \le 100$. - Subtask 4 (35 pts): No special restrictions. For $100\%$ of the testdata, $1 \le n,m \le 1000$, $1 \le q \le 5 \times 10^5$, and $1 \le a,b \le n$. **[Hints and Explanation]** **This problem is translated from [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 2 Kutije_.** **The score of this problem follows the original COCI setting, with a full score of $70$.** Translated by ChatGPT 5