Problem Description

Matrin has a collection of toys in $n$ boxes, each box labeled with a unique number from $1$ to $n$. Initially, each box contains a toy that matches its box number.

Matrin invites $m$ friends to play with these toys. Each friend, after playing, moves the toy from box $i$ to box $p_i$.

Given $q$ queries, each asking whether it is possible to arrange the toys such that the toy initially in box $a$ ends up in box $b$ after inviting friends in any order and any number of times.

Input Format

The first line contains three positive integers $n$, $m$, and $q$, representing the number of boxes/toys, friends, and queries, respectively.

The next $m$ lines each contain $n$ integers $p_i$, which is a permutation of $1$ to $n$.

The following $q$ lines each contain two integers $a$ and $b$.

Output Format

Output $q$ lines, each containing a string "DA" (yes) or "NE" (no).

Sample Input and Output

Input Sample #1

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

Output Sample #1

DA
NE
DA

Input Sample #2

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

Output Sample #2

DA
DA
NE
NE

Input Sample #3

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

Output Sample #3

DA
NE

Notes

Sample 1 Explanation:

• Query 1: Initially, toy 1 is already in box 1, so output "DA".
• Query 2: No valid scheme exists, so output "NE".
• Query 3: Inviting friend 1 suffices, so output "DA".

Data Range and Constraints:

This problem is tested with 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 "DA", there exists a scheme with at most 2 friends invited.
• Subtask 3 (10 pts): $1 \le n,m,q \le 100$.
• Subtask 4 (35 pts): No additional constraints.

For $100\%$ of the data, $1 \le n,m \le 1000$, $1 \le q \le 5 \times 10^5$, $1 \le a,b \le n$.

Translated from COCI 2021-2022 CONTEST #2 Task 2 Boxes.

This problem's score is set according to the original COCI, with a maximum of 70 points.

见题面 Input 部分

见题面 Output 部分