#531. 「LibreOJ β Round #5」游戏

内存限制:512 MiB 时间限制:1200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

LCR 三分钟就解决了问题,她自信地输入了结果……

> …… 正在检查程序 ……

> …… 检查通过,正在评估智商 ……

> 对不起,您解决问题的速度过快,与加密者的智商不符。转入精确匹配。

> 由于您在模糊匹配阶段的智商差距过大,需要进行精确匹配。匹配方法

LCR 发现,精确匹配是通过与随机对手(称为「神犇」)游戏的方式,藉由游戏的决策来评定智商的机制。游戏规则如下:

有一个长为 nn,下标为 [1,n][1,n] 的数组 f[]f[],且满足 f[i][1,n]f[i]\in [1,n]

有一个变量 aa 初始值为 11。双方轮流操作,LCR 先手。

操作方法:每次在所有满足 f[i]=af[i]=aii 中选一个,并将 aa 赋值为 ii,不能不选。无法操作者输,若共 2n2n 次操作后仍未决出胜负,则为平局。

我们定义二元关系“到达”如下:

  • ii 可以到达 ii
  • ii 可以到达 f[i]f[i]
  • 如果 ii 能到达 jjjj 能到达 kk,则 ii 能到达 kk

ff 数组满足性质:对于任意 i,ji,j 存在 kk 使得 iijj 都能到达 kk

LCR 即将面对 qq 局游戏。她发现每局游戏的 f[]f[] 数组都和给定的「模板数组」很像。经过进一步研究她发现每局游戏可以描述如下:

给出两个整数 u,vu,v满足在模板数组中 f[u]f[u] 能到达 uuf[v]f[v] 能到达 vv。则该局游戏的 f[]f[] 是把模板数组的 f[u]f[u] 赋值为 vv 后得到的。

现在 LCR 希望你帮她计算每局游戏的胜负状态。

输入格式

第一行两个正整数 n,qn,q

第二行 nn 个整数表示 f[]f[]

接下来 qq 行每行两个整数 u,vu,v 描述一局游戏。

输出格式

输出共 qq 行。

每行一个整数 rr 表示结果。 r=1r=1 表示先手(LCR)有必胜策略,r=0r=0 表示后手(神犇)有必胜策略,r=2r=2 表示平局。

样例

样例输入

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

样例输出

2
0
0

数据范围与提示

对于所有数据,1n,q1061\le n,q\le 10^6

Subtask # 分值 n,qn,q 的限制 特殊限制
1 1515 n,q4n,q\le 4
2 2727 n,q3000n,q\le 3000
3 2222 n,q2×105n,q\le 2\times 10^5 f[]f[] 是排列
4 2323 n,q2×105n,q\le 2\times 10^5
5 1313 n,q106n,q\le 10^6