说明

比特国最著名的画作——莱昂纳多·达·比特奇（Leonardo da Bitci）的《持电脑鼠标的女士肖像》——需要修复。修复工作将在两个专业分工明确的实验室中进行。修复过程被划分为若干阶段。对于每个阶段，我们知道它将在哪个实验室进行。

运输这幅极其珍贵且易碎的画作会带来额外的风险；因此，应尽可能避免运输。理想情况下，所有工作应在第一实验室完成，然后将画作转移到第二实验室。不幸的是，修复阶段之间存在一些依赖关系——某些阶段必须在其他阶段开始之前完成。你的任务是找到一个修复阶段的顺序，使得画作在两个实验室之间转移的次数最少。修复可以从两个实验室中的任意一个开始。

输入格式

输入的第一行包含测试用例的数量 $T$。随后是每个测试用例的描述：

每个测试用例的第一行包含两个空格分隔的整数 $n$ 和 $m$（$1\le n\le 100000$，$0\le m\le 1000000$）——修复阶段的数量以及它们之间的依赖关系数量。接下来一行有 $n$ 个空格分隔的整数——第 $i$ 个整数为 $1$ 表示第 $i$ 个修复阶段将在第一实验室进行，否则为 $2$。接下来的 $m$ 行每行包含一对整数 $i,j$（$1\le i,j\le n$），表示第 $i$ 个阶段必须在第 $j$ 个阶段之前完成。

你可以假设总是存在一种修复阶段的顺序，使得所有依赖关系得到满足。

输出格式

按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例，输出一行，包含画作需要在实验室之间转移的最小次数。

1
5 6
1 2 1 2 1
1 2
1 3
2 4
3 4
2 5
3 5

2

提示

翻译由 DeepSeek 完成