Byteland 最著名的画作——一幅由 Leonardo da Bitci 创作的、画中人拿着鼠标的女士肖像——需要进行修复。修复工作将在两个专业实验室中进行。修复过程被分为若干个阶段。对于每一个阶段，我们都知道它将在哪个实验室进行。

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

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $m$ ($1 \leqslant n \leqslant 100\,000, 0 \leqslant m \leqslant 1\,000\,000$)，分别表示修复阶段的数量和它们之间的依赖关系数量。下一行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个整数如果为 $1$，表示第 $i$ 个修复阶段将在第一个实验室进行，否则为 $2$。接下来的 $m$ 行包含整数对 $i, j$ ($1 \leqslant i, j \leqslant n$)，表示第 $i$ 个阶段必须在第 $j$ 个阶段之前完成。

你可以假设总能找到一种满足所有依赖关系的修复阶段排序。

输出格式

按输入中出现的顺序打印各测试用例的答案。对于每个测试用例，输出一行，包含画作在两个实验室之间需要运输的最少次数。

样例

输入 1

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

输出 1

2