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

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

题目描述

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

> …… 正在检查程序 ……

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

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

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

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

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

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

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

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

  • i 可以到达 i
  • i 可以到达 f[i]
  • 如果 i 能到达 j j 能到达 k ,则 i 能到达 k

f 数组满足性质:对于任意 i,j 存在 k 使得 i j 都能到达 k

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

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

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

输入格式

第一行两个正整数 n,q

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

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

输出格式

输出共 q 行。

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

样例

样例输入

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

样例输出

2
0
0

数据范围与提示

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

Subtask # 分值 n,q 的限制 特殊限制
1 15 n,q\le 4
2 27 n,q\le 3000
3 22 n,q\le 2\times 10^5 f[] 是排列
4 23
5 13 n,q\le 10^6