题目描述

Matrin 有 $n$ 个箱子的玩具。箱子分别用序号 $1,2,3,\cdots,n$ 表示。初始状态下，每个箱子中有一个与箱子编号相同的玩具。

Matrin 邀请了 $m$ 位朋友来家玩玩具。他注意到，每一位朋友在玩完玩具之后，都会将原先位于 $i$ 号箱子内的玩具放入 $p_i$ 号箱内。

给定 $q$ 组询问，每次可随意邀请朋友并自由选择顺序，同时每位朋友可以邀请任意多次。问是否存在一种方案，使得 $a$ 号玩具最终被放入 $b$ 号箱子中。

输入格式

第一行三个正整数 $n,m,q$，分别表示箱子 / 玩具、朋友和询问的数量。

接下来的 $m$ 行，每行 $n$ 个整数 $p_i$。数据保证 $p_i$ 是 $1 \sim n$ 的一个排列。

接下来的 $q$ 行，每行两个整数 $a,b$。

输出格式

共 $q$ 行，每行输出一个字符串 $\texttt{DA}$（是）或 $\texttt{NE}$（否）。

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

提示

【样例 1 解释】

• 询问 $1$：初始状态下，$1$ 号玩具已经在 $1$ 号箱子内，故输出 $\texttt{DA}$。
• 询问 $2$：第二组询问：无符合题意的方案，输出 $\texttt{NE}$。
• 询问 $3$：邀请 $1$ 号朋友前来即可，输出 $\texttt{DA}$。

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1（15 pts）：$m=1$。
• Subtask 2（10 pts）：$1 \le n,m,q \le 100$；对于每组询问，若答案为 $\texttt{DA}$，则保证存在一种邀请朋友数量不超过 $2$ 的方案。
• Subtask 3（10 pts）：$1 \le n,m,q \le 100$。
• Subtask 4（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$1 \le q \le 5 \times 10^5$，$1 \le a,b \le n$。

【提示与说明】

题目译自 COCI 2021-2022 CONTEST #2 Task 2 Kutije。

本题分值按 COCI 原题设置，满分 $70$。