406820: GYM102565 I Soldiers

To prepare for emergencies, the king has given you the most important task: improving the defence of the country's army!

The country can be visualized as a graph with $$$1 \leq N \leq 10^5$$$ nodes and $$$1 \leq M \leq 2*10^5$$$ undirected edges. Each node also has a risk $$$1 \leq R[i] \leq 10^8$$$ of collapsing.

Among this country, there are also $$$1 \leq S \leq 2*10^5$$$ soldiers. For each of them you know the node they are situated in and also its type. All soldier types are numbers that fit within 32 bit signed integers.

In case of emergency, each soldier should have an emergency contact to help. Therefore, you must construct a matching of all soldiers such that you only match soldiers of the same type and each soldier is matched to exactly one other soldier. It is guaranteed that such matching exists.

Furthermore, you would like to minimize the sum of risks for each pair in the matching. The risk of a pair is defined as the sum of risks of all the nodes $$$X$$$ such that if $$$X$$$ is removed from the graph, the two paired soldiers can no longer reach each other(this includes the nodes where the soldiers are initially situated in). If 2 soldiers are situated in the same node, the risk of their pairing is the risk of that node.

The first line of the input will contain $$$2$$$ numbers $$$N$$$ and $$$M$$$, representing the number of nodes and edges respectively.

The following line will contain $$$N$$$ numbers, the array $$$R$$$.

The next $$$M$$$ lines each contain $$$2$$$ numbers $$$X$$$ and $$$Y$$$, meaning there is an undirected edge between $$$X$$$ and $$$Y$$$.

The next line contains $$$S$$$, the number of soldiers. The following $$$S$$$ lines each contain a pair of numbers: the node in which the soldier is situated and its type.

You should output one line containing one integer: the minimum risk of a valid pairing. You may assume that there always exists a valid pairing.

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

38

To obtain this answer, you should pair soldiers in nodes 1-2, 4-8 and 5-6.

For pair 1-2, the nodes we sum the risks of are 1 and 2.

For pair 4-8, the nodes we sum the risks of are 4, 5, 7 and 8.

Finally, for pair 5-6, the nodes we sum the risks of are 5 and 6.