Conservation

The most famous painting in Byteland — a portrait of a lady holding a computer mouse, painted by Leonardo da Bitci — needs to be conserved. The work will be carried out in two highly specialized laboratories. The conservation process is divided into several stages, and for each stage we know the laboratory in which it must be performed.

Because the painting is extremely precious and fragile, transporting it between the laboratories adds risk and should be avoided whenever possible. Ideally, all of the work belonging to one laboratory would be finished first, and only then would the painting be moved to the other. Unfortunately, there are dependencies between the stages: some stages must be completed before others may begin. Your task is to order the conservation stages so that the number of times the painting is moved from one laboratory to the other is as small as possible. The conservation may begin in either laboratory.

The first line contains the number of test cases T. The test cases follow.

The first line of each test case contains two space-separated integers n and m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 1 000 000) — the number of conservation stages and the number of dependencies between them. The next line contains n space-separated integers; the i-th of them is 1 if the i-th stage takes place in the first laboratory and 2 otherwise. Each of the following m lines contains a pair of integers i and j (1 ≤ i, j ≤ n), meaning that the i-th stage must be completed before the j-th stage.

It is guaranteed that the stages can always be ordered so that all dependencies are satisfied.

For each test case, print a single line with the minimum number of times the painting must be transported between the two laboratories. Print the answers in the order the test cases appear in the input.