Problem Statement:

Omar El-Mohandes decided to leave his career in programming and pursue his dream to become a children party entertainer (a.k.a. a clown). Each day he visits birthdays and parties, wearing colorful costumes (clown, batman, spiderman ...) , and makes children happy!

As usual, he excelled in his new job, and became very famous very quickly. Lots of children want him to attend their event each day, and Omar hates refusing a child's request. Each child requests two things from him in his/her event:

- to wear a certain costume (e.g. batman)

- to come to their event at any time, as long as it's before a list of events of children they hate.

Fortunately, there are no circles of hate, and he can always attend all events. But he takes his costumes very seriously, preparing every small detail. If two consecutive events require the same costume, Omar will not need to change between them. Otherwise, Omar will have to change. He never wears the same copy of the costume twice, meaning that he might have to buy several copies of the same costume type depending on the order of the events he will attend. As you might expect, this can be really expensive, but it is always one costume type only that is expensive, and the rest are really cheap. But he doesn't know which one will be the most expensive yet. Could you help him prepare for all possible scenarios? In particular, can you help him find the minimum number of copies of each costume type he needs to buy if it was the most expensive one?

Input Format:

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T test cases. Each test case will consist of several lines. The first line will contain two integers, separated by a single space: N, M (1 ≤ N ≤ 500, 0 ≤ M ≤ [N * (N - 1)] / 2), the number of events to attend, and number of hate relationship between the children respectively. The next line will contain N integers, separated by a single space: k_{i} (1 ≤ k_{i} ≤ N) the type costume you have to wear for i-th event. The next M lines will contain two integers separated by space: a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ N, a_{i} ≠ b_{i}), which means the child in event a_{i} hates the child in event b_{i}, and you must go to the first event before the second event.

Output Format:

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1). Then K lines follow (where K is the number of unique costume types in the input). For each line, output the minimum number of costumes of type k_{i}. The lines must be ordered by the custom type.

Sample Input:

1
10 10
1 2 1 2 3 1 1 2 3 1
1 2
1 3
2 4
2 5
5 10
4 6
7 8
8 9
9 10
3 5

Sample Output:

Case 1:
2
1
1