405592: GYM102006 E 2Nodes

Mr. Light is playing an online game which involves a connected undirected graph. Each node is colored in either white, red, or blue.

When Mr. Light presses the start button, at every second, every white node with a non-white adjacent node will be colored in the same color as that adjacent node. If there are multiple such adjacent nodes, the color of the one with the minimum index is chosen. The game ends when there are no longer any white nodes. All color changes in the same second occur simultaneously.

Before pressing the start button, Mr. Light is given the opportunity to choose a maximum of two non-white nodes, and color them white. Can you help him choose at most two nodes such that when the game ends, the number of nodes that are colored red is maximized?

The first line of input contains a single integer T (1 ≤ T ≤ 1024), the number of test cases.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 10⁵) (n - 1 ≤ m ≤ 10⁵), the number of nodes and the number of edges, respectively.

The second line contains n space-separated integers c_i (0 ≤ c_i ≤ 2), where c_i = 0 if the i^th node is white, c_i = 1 if it is red, and c_i = 2 if it is blue. It is guaranteed that there's at least one red node.

Each of the following m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), representing an undirected edge between the nodes u and v.

It is guaranteed that the graph is connected and contains no self-loops or multiple edges.

The sum of m over all test cases doesn't exceed 5 × 10⁶.

For each test case, output a single line with the maximum number of nodes that will be colored red after changing the color of at most two non-white nodes to white.

2
1 0
1
8 12
0 2 2 2 0 1 1 0
4 6
7 5
5 8
3 2
1 2
5 4
2 5
2 7
3 7
6 2
8 4
1 4

1
5