Malware Spread

Source: Flexport #6 Malware Spread. Delete exactly one network node together with its incident edges, then let the infection spread along undirected edges from every initially infected node that was not deleted, until no new node gets infected. Find the deletion that minimizes the final number of infected nodes; on ties, choose the smallest 1-based index. Taken literally, the original problem allows any node in the network as a candidate, including healthy nodes.

输入格式

The first line contains n m; the second line contains n initial infection flags, each 0/1; each of the next m lines contains a 1-based undirected edge u v. 1≤n≤1000, 0≤m≤min(n(n−1)/2,1000); this site treats the graph as simple (no multi-edges or self-loops).

输出格式

Output the 1-based index of the node to delete. Even if no node is infected, one node must still be deleted; on ties, output the smallest index.

样例 1

输入：

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

输出：

3

样例 2

输入：

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

输出：

1

样例 3

输入：

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

输出：

3

样例说明

Public example 1 is re-simulated on the graph and infected nodes given in the problem: deleting node 3 minimizes the infected count, so the output is 3. In public example 2, the remaining nodes stay infected no matter which node is deleted, so the smallest index 1 is chosen. This site's rules explicitly allow deleting a healthy node; the third example, a regression case added by this site, specifically tests a healthy cut vertex.