408905: GYM103373 I ICPC Kingdom

The ICPC kingdom has $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and there are $$$m$$$ roads, numbered from $$$1$$$ to $$$m$$$, connecting these cities. Each road connects two cities, and people can travel along the roads in both directions. There are $$$a_i$$$ residents living in city $$$i$$$. Road $$$j$$$ connects city $$$u_j$$$ and city $$$v_j$$$. And the economic benefit of road $$$j$$$ is $$$\left\lfloor\sqrt{a_{u_j}+a_{v_j}}\right\rfloor$$$.

One day, the enemy invaded the ICPC kingdom and destroyed all roads. Fortunately, the ICPC troops defeated the enemy and stopped the invasion. To recover from the war, the king of ICPC hired $$$w$$$ workers to fix the roads. Each worker can fix at most one road, and the $$$i$$$-th worker can only fix one of the roads whose indices are among $$$b_1,b_2,\dots,b_{x_i}$$$.

Now the king wants to fix the roads to make the kingdom normal. Considering the cost, the king does not want the repair plan containing any useless road. If a repair plan contains a useless road, there exists a pair of city $$$p$$$ and $$$q$$$ such that there is more than one simple path from city $$$p$$$ to city $$$q$$$. A simple path is a sequence of distinct roads $$$c_1,c_2,\dots,c_z$$$ such that a trip along $$$c_1,c_2,\dots,c_z$$$ will visit exactly $$$z+1$$$ distinct cities.

The king asked you to calculate the maximum economic benefit if exactly $$$k$$$ roads are fixed without useless roads. You need to calculate for each $$$k$$$ between $$$1$$$ and $$$n-1$$$.

The first line contains $$$n$$$ and $$$m$$$ separated by a white space. $$$n$$$ is the number of cities, and $$$m$$$ is the number of roads. The second line contains $$$n$$$ numbers $$$a_1,a_2,a_3...a_n$$$ separated with white spaces indicating the number of the residents in cities $$$1,2,\dots,n$$$, respectively. There are $$$m$$$ lines following; each line contains $$$u_j$$$ and $$$v_j$$$ separated with white space. Road $$$j$$$ connects city $$$u_j$$$ and city $$$v_j$$$. The third line contains a number $$$w$$$ indicating the number of workers. The following $$$w$$$ line indicates the roads that can be fixed by the workers. The $$$(3+i)$$$-th line contains several numbers separated by spaces. The first number is $$$x_i$$$ indicating the number of roads that the $$$i$$$-th worker can fix. There are $$$x_i$$$ distinct integers $$$b_1,b_2,\dots,b_{x_i}$$$. following in that line. The $$$i$$$-th worker can only fix one of roads $$$b_1,b_2,\dots,b_{x_i}$$$.

• $$$1\leq n \leq 100$$$
• $$$0\leq m \leq 100$$$
• $$$1\leq a_i \leq 10^9$$$
• $$$1\leq u_i,v_i \leq n, u_i\neq v_i$$$
• $$$0\leq w \leq 100$$$

Print $$$n-1$$$ numbers. The $$$i$$$-th number printed is the the maximum economic benefit if the repair plan fixes exactly $$$i$$$ roads without useless roads; if there is no such plan, you should print $$$-1$$$.

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

2 3 4 -1