eolymp
bolt
Try our new interface for solving problems
Problems

Conservation

Conservation

Time limit 6 seconds
Memory limit 256 MiB

The most famous painting in Byteland — a portrait of a lady with acomputer mouse by Leonardo da Bitci — needs to be conserved. The work will be conducted in two narrowly specialized laboratories. The conservation process has been divided into several stages. For each of them, we know the laboratory in which it will take place.

Transporting the very precious and fragile painting introduces additional risk; therefore, it should be avoided whenever possible. Ideally, all the work in the first laboratory would be done, and then the painting would be moved to the second one. Unfortunately, there are several dependencies between the conservation stages — some of them need to be completed before others may begin. Your task is to find an ordering of conservation stages that minimizes the number of times the painting needs to be moved from one laboratory to the other. The conservation can begin in any of the two laboratories.

Input data

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

The first line of each test case contains two space-separated integers n and m (1n100000, 0m1000000) —the number of conservation stages and the number of dependencies between them. In the next line there are n space-separated integers — the i-th of them is 1 if the i-th conservation stage will take place in the first laboratory, and 2otherwise. The following m lines contain pairs of integers i, j (1i, jn), denoting that the i-th stage has to be completed before the j-th.

You may assume that it is always possible to order the conservation stages so that all the dependencies are satisfied.

Output data

Print the answers to the test cases in the order in which they appear in the input. For each test case, output a single line containing the minimal number of times the painting needs to be transported between the laboratories.

Examples

Input example #1
1
5 6
1 2 1 2 1
1 2
1 3
2 4
3 4
2 5
3 5
Output example #1
2
Source Central Europe Regional Contest 2012, Kraków, November 16-18, 2012