Navy

Byteland has $N$ lakes, and some rivers directly connect pairs of lakes. You are the naval commander of Byteland, and you want to plan a strategy for the coming war.

Byteland's intelligence service reports that the war will last $T+1$ days, and that a battle takes place on each night between consecutive days. That is, for every $1 \le i \le T$, a battle takes place on the night between day $i$ and day $i+1$.

Treat the lakes and rivers of Byteland as a graph. If removing a river increases the number of connected components, the river is called a critical river. (In graph theory, such a river is called a cut edge.)

Lakes always hold water, but rivers may dry up depending on the weather. That is, a pair of lakes may or may not be directly connected by a river. Byteland has $M$ kinds of weather, and weather $i$ creates a river for each pair of lakes in the set $A_i$.

Scientists found the weather $B_i$ for each day $i$ from $1$ to $T+1$. Scientists predicted that on the night between day $i$ and day $i+1$, when a battle takes place, the set of rivers is $A_{B_i} \cup A_{B_{i+1}}$.

Using these predictions, output the number of critical rivers for each of the $T$ battles.

A set may contain the same element two or more times (a multiset), and the lakes and rivers may not form a planar graph.

The first line contains three integers $N$, $M$, and $T$. ($1 \le N, M \le 100\,000$, $1 \le T \le 200\,000$)

The second line contains $T+1$ integers $B_1, B_2, \ldots, B_{T+1}$. ($1 \le B_i \le M$)

The next $M$ lines describe the sets $A_i$. Each line contains $2K_i + 1$ integers. The first integer is the size $K_i$ of $A_i$. The next $2K_i$ integers list, in order, the numbers of the lakes that each pair of lakes in that weather connects. The two lake numbers in each pair are different.

The sum of all $K_i$ does not exceed $200\,000$.

Print $T$ lines. Line $i$ contains the number of critical rivers for the $i$-th battle.