P9615 [CERC2019] Saba1000kg

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[Saba1000kg](https://contest.felk.cvut.cz/19cerc/solved/saba.pdf)”.**

There are many different styles in Viking rock sport. Ancient Icelandic granite rock, medieval dusty Danish Viking rock, late Fingal dark green rock, fjord boulder avalanche rock, and many other rocks... A complete list of all popular styles would overflow this page several times. The Scandinavian Ministry of Higher Education has studied how the different styles influence each other. They are currently planning a large experiment, where some carefully selected volunteers will be distributed across an archipelago of uninhabited small islands, and the researchers hope to observe the mutual influence between their rock styles and preferences over a relatively long period of time. The inhabitants of an island always influence each other. Some pairs of islands are close enough that their inhabitants can influence each other, while the distance between other pairs of islands prevents any direct influence. In the latter case, if one or more other islands are inhabited and pass on influence, the inhabitants of these islands may still influence each other, but only indirectly. There are several proposals for how to distribute the volunteers among the islands. For each proposal, the ministry wants to know the number of independent groups of inhabitants that the archipelago will form. Two groups of island inhabitants, each occupying one or more islands, are considered independent if it is not possible for them to influence each other, not even indirectly (translator’s note: here, an “independent group of inhabitants” is defined as a set of inhabited islands whose residents cannot be influenced by residents of any other group, either directly or indirectly). Help the ministry evaluate their proposals.

The first line contains three integers $N, E, P\ (1\le N\le 10^5, 0\le E\le 10^5, 1\le P\le 10^5)$. $N$ is the number of islands in the archipelago, $E$ is the number of island pairs that allow direct influence, and $P$ is the number of proposals to evaluate. The islands are numbered from $1$ to $N$. The next $E$ lines specify pairs of islands that are allowed to influence each other directly. Each of these lines contains two integers $A$ and $B$, denoting the numbers of two different islands. No pair of islands appears more than once. The next $P$ lines each describe one proposal. Each line starts with the number of inhabited islands $M\ (1\le M\le N)$ in that proposal, followed by $M$ pairwise distinct island numbers that are inhabited. According to the proposal, no other islands are inhabited (translator’s note: that is, only the islands in each query are considered for whether influence can be passed on). The sum of the sizes of all proposals (all numbers $M$) does not exceed $10^5$.

For each proposal, output one line containing the number of independent groups that the archipelago will form.

Translated by ChatGPT 5