[CERC2019] Saba1000kg

Luogu

IDLGP9615

Time500ms

Memory128MB

Difficulty—

2019O2优化ICPCCERC

维京岩石运动中有许多不同的风格。古老的冰岛花岗岩石、中世纪丹麦尘土飞扬的维京岩石、晚期芬盖尔深绿色岩石、峡湾巨石雪崩岩石和许多其他岩石……所有受欢迎的风格的完整列表会多次溢出本页。斯堪的纳维亚高等教育部研究了各种风格之间相互影响的方式。他们目前正在计划一项大型实验，届时将有一些经过适当选择的志愿者分布在一个由无人居住的小岛组成的群岛上，研究人员希望在相对较长的一段时间内观察他们的岩石风格和偏好的相互影响。一个岛上的居民总是相互影响。一些岛对距离足够近，他们的居民可以相互影响，而其他岛对之间的距离可以防止任何直接影响。在后一种情况下，如果有一个或多个其他岛屿有人居住并传递影响，这些岛屿的居民仍然可以相互影响，但只能间接影响。关于志愿者在各岛屿之间的分配，有几个提案。对于每一种提案，该部都想知道该群岛将形成的独立居民群体的数量。两组岛屿居民，每一组都占据一个或多个岛屿，如果他们不可能相互影响，甚至不是以间接的方式，也被视为独立的（译者注：此处定义了“与其他居民群体独立的居民群体”为无法被其他居民直接或间接影响的居民的岛屿）。帮助该部评估他们的提案。 ## Input 第一行包含三个整数 $N, E, P\ (1\le N\le 10^5, 0\le E\le 10^5, 1\le P\le 10^5)$。$N$ 是群岛中的岛屿数量，$E$ 是允许直接影响的岛对数量，$P$ 是要评估的提案数量。这些岛被从 $1$ 到 $N$ 标号。接下来 $E$ 行指定允许直接相互影响的岛对。这些行中的每一行包含两个整数 $A$ 和 $B$，表示两个不同岛的标号。没有岛对出现超过一次。接下来 $P$ 行，每行都描述了一个提案。每行以该提案下居住的岛屿数量 $M\ (1\le M\le N)$ 开始，然后包含 $M$ 个居住岛屿的成对不同标号。根据各自的提案，不会有其他岛屿居住（译者注：即只考虑每次询问的岛屿能否传递影响）。所有提案的大小之和（所有数字 $M$）不超过 $10^5$。 ## Output 对于每个提案，输出一行，代表该群岛将形成的独立群体的数量。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Saba1000kg](https://contest.felk.cvut.cz/19cerc/solved/saba.pdf)」**

Samples

Input #1

Output #1

2
1
1

Input #2

5 1 1
1 2
5 5 4 3 2 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CERC2019] Saba1000kg",
    "description": {
      "content": "维京岩石运动中有许多不同的风格。古老的冰岛花岗岩石、中世纪丹麦尘土飞扬的维京岩石、晚期芬盖尔深绿色岩石、峡湾巨石雪崩岩石和许多其他岩石……所有受欢迎的风格的完整列表会多次溢出本页。斯堪的纳维亚高等教育部研究了各种风格之间相互影响的方式。他们目前正在计划一项大型实验，届时将有一些经过适当选择的志愿者分布在一个由无人居住的小岛组成的群岛上，研究人员希望在相对较长的一段时间内观察他们的岩石风格和偏好的相",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9615"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "维京岩石运动中有许多不同的风格。古老的冰岛花岗岩石、中世纪丹麦尘土飞扬的维京岩石、晚期芬盖尔深绿色岩石、峡湾巨石雪崩岩石和许多其他岩石……所有受欢迎的风格的完整列表会多次溢出本页。斯堪的纳维亚高等教育部研究了各种风格之间相互影响的方式。他们目前正在计划一项大型实验，届时将有一些经过适当选择的志愿者分布在一个由无人居住的小岛组成的群岛上，研究人员希望在相对较长的一段时间内观察他们的岩石风格和偏好的相...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments