Post Office Investigation

All international mail arriving in this country is first collected at the central post office. From there it is relayed through other post offices until it reaches the destination office. The delivery routes are described by a directed graph $G = (V, E)$, where $V$ is the set of post offices and $E$ is the set of possible forwarding steps. The operation is not efficient, so mail does not necessarily travel along a shortest route.

The post offices split into groups. A group is a set of post offices in which mail can go from any member to any other member, either directly or through other offices. A group holds at most 10 post offices.

Customers often complain that mail has not arrived. The cause is usually a system fault in one single post office, but finding that office is not easy. When such complaints come in, customer support sends staff to check the system of each candidate office. Checking post office $u$ costs $c_u$, which depends on the size of the office.

The country has many post offices and complaints arrive often, so the postal administration wants to keep the investigation cost down. It uses the following rule. If post offices $w_1, \dots, w_k$ report complaints on one day, then on the next day staff investigate the single office $v$ with the smallest investigation cost among the candidates. Office $v$ is a candidate if every route from the central post office to each of $w_1, \dots, w_k$ passes through $v$. If nothing is wrong at $v$, the order of investigating the remaining offices is decided on some later day, which is not part of this problem.

A route from the central post office to $w$ starts at office 1 and ends at office $w$, so both of those offices count as offices the route passes through.

Given the list of complaining offices for one day as a query, print the cost of the cheapest candidate.

The input holds one test case in the following format.

n m
u_1 v_1
...
u_m v_m
c_1
...
c_n
q
k_1 w_1,1 ... w_1,k_1
...
k_q w_q,1 ... w_q,k_q

$n$ is the number of post offices ($2 \le n \le 50\,000$), numbered 1 to $n$. Post office 1 is the central post office. $m$ is the number of forwarding pairs ($1 \le m \le 100\,000$). The pair $u_i$, $v_i$ means that some of the mail received at post office $u_i$ is forwarded to post office $v_i$. $c_j$ is the investigation cost of post office $j$ ($1 \le c_j \le 10^9$). $q$ is the number of queries ($q \ge 1$), and each query is a list of post offices that received complaints about undelivered mail. $k_i$ is the length of the $i$-th list ($k_i \ge 1$), and $w_{i,1}, \dots, w_{i,k_i}$ are distinct post offices. The sum of $k_i$ over all queries is at most $50\,000$.

There is at least one delivery route from the central post office to every post office. No group of mutually reachable post offices holds more than 10 offices.

For each query, print on one line the lowest investigation cost among the candidates.