ICPC 왕국 도로 복구

ICPC 왕국에는 1번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있고, 이 도시들을 잇는 1번부터 $m$번까지 번호가 붙은 $m$개의 도로가 있다. 각 도로는 두 도시를 잇고, 사람들은 도로를 양방향으로 오갈 수 있다. 도시 $i$에는 $a_i$명의 주민이 살고 있다. 도로 $j$는 도시 $u_j$와 도시 $v_j$를 잇는다. 도로 $j$의 경제적 이익은 $\left\lfloor \sqrt{a_{u_j} + a_{v_j}} \right\rfloor$이다.

어느 날 적이 왕국을 침입해 모든 도로를 파괴했다. 다행히 ICPC 군대가 적을 물리치고 침입을 막아냈다. 전쟁 복구를 위해 ICPC의 왕은 $w$명의 작업자를 고용해 도로를 수리하게 했다. 각 작업자는 최대 한 개의 도로만 수리할 수 있다. $i$번째 작업자는 $b_1, b_2, \dots, b_{x_i}$ 번 도로 중 한 개만 수리할 수 있다.

왕은 수리 계획에 쓸모없는 도로가 포함되는 것을 원하지 않는다. 두 도시 $p$와 $q$ 사이에 단순 경로가 둘 이상 있는 쌍이 존재하면, 그 계획에는 쓸모없는 도로가 포함된 것이다. 단순 경로는 서로 다른 도로의 열 $c_1, c_2, \dots, c_z$이며, 이 경로를 따라 이동하면 정확히 $z + 1$개의 서로 다른 도시를 방문한다.

왕은 쓸모없는 도로 없이 정확히 $k$개의 도로를 수리했을 때의 최대 경제적 이익을 계산해 달라고 요청한다. $k$는 1부터 $n - 1$까지 각각에 대해 계산해야 한다.

첫째 줄에 공백으로 구분된 $n$과 $m$이 주어진다. $n$은 도시의 수, $m$은 도로의 수이다. 둘째 줄에는 도시 $1, 2, \dots, n$의 주민 수 $a_1, a_2, \dots, a_n$이 주어진다. 이어지는 $m$개의 줄에는 각각 $u_j$와 $v_j$가 주어지며, 도로 $j$가 도시 $u_j$와 $v_j$를 잇는다. 다음 줄에는 작업자의 수 $w$가 주어진다. 이어지는 $w$개의 줄은 작업자가 수리할 수 있는 도로를 나타낸다. $(3 + i)$번째 줄의 첫 수 $x_i$는 $i$번째 작업자가 수리할 수 있는 도로의 개수이고, 그 뒤에 서로 다른 정수 $b_1, b_2, \dots, b_{x_i}$가 이어진다. $i$번째 작업자는 이 도로들 중 한 개만 수리할 수 있다.

$n - 1$개의 수를 출력한다. $i$번째 수는 쓸모없는 도로 없이 정확히 $i$개의 도로를 수리했을 때의 최대 경제적 이익이다. 그런 계획이 없으면 -1을 출력한다.

• $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$