题目描述

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$。