J. Burrows and ferrets
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a system of $$$N$$$ underground burrows connected by $$$M$$$ directed tunnels. The burrows are numbered from $$$1$$$ to $$$N$$$. The tunnels are one-way to avoid congestion. The only entrance from the surface is burrow $$$1$$$, and every burrow is reachable from burrow $$$1$$$.

Ferrets live in these burrows. They plan to choose some burrows as sleeping burrows and one additional burrow as an emergency supply storage. For safety, once the supplies are placed, ferrets are not allowed to enter the storage burrow, so any route that goes through that burrow cannot be used.

The ferrets want to simulate $$$Q$$$ different scenarios. In each scenario, you are given $$$k$$$ burrows that would serve as sleeping burrows. Your task is to determine how many burrows could be chosen as the supply storage burrow such that it is still possible to travel from burrow $$$1$$$ to all sleeping burrows without passing through the chosen supply storage burrow. Note that it is not possible to select burrow $$$1$$$ or any sleeping burrow as the supply storage burrow.

Help the ferrets find the answer for all scenarios.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$ and $$$0 \leq M \leq 2 \cdot 10^5$$$)  — the number of burrows and the number of tunnels.

The following $$$M$$$ lines describe the tunnels. Each of these lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq N$$$ and $$$u \neq v$$$) describing a directed tunnel from burrow $$$u$$$ to burrow $$$v$$$. It is guaranteed that all directed tunnels are distinct.

The following line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2 \cdot 10^5$$$)  — the number of scenarios.

The following $$$Q$$$ lines describe each scenario. Each line contains an integer $$$k$$$ at the beginning ($$$1 \leq k \leq N$$$) indicating the number of sleeping burrows. Then $$$k$$$ different integers $$$u_1,u_2,\dots,u_k$$$ ($$$1 \leq u_i \leq N$$$) follow in the same line  — the sleeping burrows.

It is guaranteed that the sum of $$$k$$$ over all scenarios is not greater than $$$4 \cdot 10^5$$$.

It is guaranteed that all the burrows are reachable from burrow $$$1$$$.

Output

For each scenario, print an integer indicating the number of burrows that can be used as supply storage burrow.

Examples
Input
5 5
1 2
2 3
3 4
4 5
5 1
5
1 1
1 2
1 3
1 4
1 5
Output
4
3
2
1
0
Input
4 4
1 2
1 3
2 4
3 4
2
1 4
2 2 3
Output
2
1