题目描述
小 A 和小 B 来到了古神的宫殿。
他们在墙上发现了 $2n$ 个不超过 $n$ 的正整数 $f_1,f_2,\ldots,f_n,g_1,g_2\ldots,g_n$。
他们在地上发现了 $m$ 块石板,第 $i$ 块石板上写了两个不超过 $n$ 的正整数 $x_i,y_i$。
根据传说,每过一秒, $x_i$ 就会变为 $f_{x_i}$,$y_i$ 就会变为 $g_{y_i}$。而当 $x_i=y_i$ 时(包括初始时),第 $i$ 块石板就会裂开。
小 A 想分别知道每块石板是否会裂开,但他觉得一直等下去太慢了。
小 B 让小 A 别急,但小 A 很急,你也很急,所以你要在一秒内帮小 A 找到答案。
输入格式
第一行包括两个正整数 $n,m$。
第二行包括 $n$ 个正整数 $f_1,f_2\ldots,f_n$。
第三行包括 $n$ 个正整数 $g_1,g_2\ldots,g_n$。
接下来 $m$ 行,第 $i$ 行包括两个正整数 $x_i,y_i$。
输出格式
共 $m$ 行,若第 $i$ 个石块最终会裂开就在第 $i$ 行输出 YES
,否则输出 NO
。
样例
样例输入 1
4 3
2 3 4 2
2 4 4 1
1 2
1 4
3 3
样例输出 1
NO
YES
YES
样例解释 1
对于第一块石板,可以证明它永远不会裂开。
对于第二块石板,$(x_2,y_2)$ 的变化为 $(1,4)\rightarrow(2,1)\rightarrow(3,2)\rightarrow(4,4)\rightarrow\cdots$,于是它会在三秒之后裂开。
对于第三块石板,它会在一开始就裂开。
样例输入 2
10 10
3 8 7 3 7 6 4 1 9 10
3 3 2 6 7 6 5 5 10 10
1 5
10 4
10 2
7 6
8 7
3 4
10 5
5 5
2 6
8 5
样例输出 1
YES
NO
NO
NO
YES
NO
NO
YES
NO
YES
样例输入 / 输出 3
见下发文件中的 ex_wait3.in/ex_wait3.ans
,该样例满足子任务 3 的特殊性质。
样例输入 / 输出 4
见下发文件中的 ex_wait4.in/ex_wait4.ans
,该样例满足子任务 5 的特殊性质。
样例输入 / 输出 5
见下发文件中的 ex_wait5.in/ex_wait5.ans
,该样例满足子任务 6 的特殊性质。
样例输入 / 输出 6
见下发文件中的 ex_wait6.in/ex_wait6.ans
,该样例满足子任务 7 的特殊性质。
数据范围
本题采用捆绑测试。
对于所有数据 $1\le n,m\le 10^5,1\le f_i,g_i,x_i,y_i\le n$。
子任务编号 | $n,m\le$ | $f$ | $g$ | 子任务分值 |
---|---|---|---|---|
1 | $10$ | - | - | 3 |
2 | $100$ | 7 | ||
3 | $1000$ | 11 | ||
4 | $10^5$ | * | * | 5 |
5 | A | A | 17 | |
6 | B | 17 | ||
7 | B | 17 | ||
8 | - | - | 23 |
对于某个子任务,若其表格中 $h$ ($h$ 为 $f$ 或 $g$)这一列为:
- A,则满足 $\forall 1\le i< j\le n,h_i\ne h_j$。
- B,则满足 $\forall 1\le i\le n,h_i\le i$。
- *,则该子任务(子任务 4)满足 $\forall 1\le i\le n,f_i=g_i$。
- -,则无特殊限制。