Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
Saba1000kg
saba.c, saba.cpp, Saba.java, saba.py
There are many different streams in Viking rock movement. Old Icelandic granite rock, Mid-
dle Danish dusty Viking rock, Late Finngail dark green rock, Fjord boulder avalanche rock,
and many others, a complete list of all popular streams would overflow this page many times.
The Scandinavian Ministry of Higher Education studies various ways the streams influence each
other. They are currently planning a huge experiment, when a number of suitably chosen vol-
unteers will be distributed over an archipelago of uninhabited small islands, and the researchers
want to observe the mutual influence of their rock styles and preferences over a relatively long
period of time.
The inhabitants on one island will always influence each other. Some pairs of the islands are
situated close enough for their inhabitants to influence each other, while the distances between
other pairs prevent any direct influence. In the latter case, the inhabitants of such islands may
still influence each other, but only indirectly, if there are one or more other islands that are
inhabited and relay the influence.
There are several proposals on the distribution of the volunteers among the islands. For each of
these distributions, the Ministry would like to know the number of independent groups of inhab-
itants that will form in the archipelago. Two groups of island inhabitants, each occupying one
or more islands, are considered independent, if there is no possibility of their mutual influence,
not even in the indirect way.
Help the Ministry to evaluate their proposals.
Input Specification
The first input line contains three integers, N , E, P (1 ≤ N ≤ 105, 0 ≤ E ≤ 105, 1 ≤ P ≤ 105).
N is the number of islands in the archipelago, E is the number of pairs of islands that allow
direct influence, and P is the number of proposals to be evaluated. The islands are labeled from
1 to N .
The next E lines specify the pairs of islands that allow direct mutual influence. Each of these
lines contains two integers A and B denoting the labels of two different islands. No pair of
islands occurs more than once.
Each of the next P lines describes one proposal. Each line starts with a number of islands
inhabited under that proposal M (1 ≤ M ≤ N ) and then contains pairwise distinct labels of M
inhabited islands. No other island will be inhabited under the respective proposal.
The sum of the sizes of all proposals (all numbers M ) does not exceed 105 .
Output Specification
For each proposal, print a line with the number of independent groups that will form in the
archipelago.
Output for Sample Input 1
Sample Input 1
2
4
43
1
1
2
1
3
1
1
4
3
4
3
234
1
1
4
1234
Sample Input 2
Output for Sample Input 2
511
4
12
554321
