ICPC Kingdom

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

One day, an 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}$.

The king does not want the repair plan to contain any useless road. A plan contains a useless road if there exist cities $p$ and $q$ with more than one simple path between them. 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$ visits exactly $z + 1$ distinct cities.

The king asks you to calculate the maximum economic benefit when exactly $k$ roads are fixed without useless roads. Calculate it for each $k$ from $1$ to $n - 1$.

The first line contains $n$ and $m$ separated by a space. $n$ is the number of cities, and $m$ is the number of roads. The second line contains $a_1, a_2, \dots, a_n$, the number of residents in cities $1, 2, \dots, n$. The next $m$ lines each contain $u_j$ and $v_j$, meaning road $j$ connects cities $u_j$ and $v_j$. The next line contains $w$, the number of workers. The following $w$ lines describe the roads each worker can fix. The $(3 + i)$-th line starts with $x_i$, the number of roads the $i$-th worker can fix, followed by $x_i$ distinct integers $b_1, b_2, \dots, b_{x_i}$. The $i$-th worker can fix only one of these roads.

Print $n - 1$ numbers. The $i$-th number is the maximum economic benefit when the repair plan fixes exactly $i$ roads without useless roads. If no such plan exists, print -1 for that $i$.

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