3982: 「LibreOJ β Round #5」游戏

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$，$f[v]$ 能到达 $v$**。则该局游戏的 $f[]$ 是把模板数组的 $f$ 赋值为 $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