Problem Description

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$.

Input Format

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 Format

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

4 1 3
1 2 4 3
1 1
1 2
3 4

DA
NE
DA

4 2 4
2 1 3 4
1 2 4 3
2 1
3 4
1 4
2 3

DA
DA
NE
NE

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

DA
NE

Hint

[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 CONTEST #2 Task 2 Kutije.

The score of this problem follows the original COCI setting, with a full score of $70$.

Translated by ChatGPT 5