← 返回题目列表

Codeforces · 223/E

E. 平面图

中文机器翻译题面 查看原题

如果一个图可以以其边仅在顶点相交的方式绘制,则该图被称为平面图。

关节点是无向图的顶点,当移除该顶点时,图的连通分量的数量会增加。

桥是无向图的边,当被移除时,图的连接组件的数量会增加。

你有一个连通的无向平面图,由 n 个顶点组成,编号从 1 到 n,绘制在平面上。该图没有桥、连接点、循环和多重边。您还会收到 q 个查询。每个查询都是图中的一个循环。查询响应是图形顶点的数量,这些顶点(如果您在平面上绘制图形和循环)位于循环内部或循环之上。编写一个程序,根据给定的图形和查询,它将回答每个查询。

输入

第一行包含两个空格分隔的整数 n 和 m (3 ≤ n, m ≤ 105) — 图的顶点和边的数量。接下来的 m 行包含图的边:第 i 行包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n) — 连接第 i 条边的顶点数。接下来的 n 行包含平面图顶点在平面上的位置:第 i 行包含一对空格分隔的整数 xi 和 yi (|xi|, |yi| ≤ 109) — 平面上图的第 i 个顶点的坐标。

下一行包含整数 q (1 ≤ q ≤ 105) — 查询数。然后是描述查询的 q 行:第 i 行包含空格分隔的整数序列 ki, a1, a2, ..., aki (1 ≤ aj ≤ n; ki > 2),其中 ki 是第 i 个查询中的循环长度,aj 是形成循环的顶点数。循环中的顶点数按顺时针或逆时针顺序给出。给定的循环很简单,即它们不能多次经过图顶点。所有查询中所有循环的总长度不超过105。

保证给定的图不包含桥、关节点、循环和多重边。保证边段仅在图的顶点处可以有公共点。

输出

对于每个查询,打印一个整数 - 循环内部或循环上的顶点数。按顺序打印答案,其中查询紧随输入。用空格分隔数字。

示例

输入 #1

3 3
1 2
2 3
3 1
0 0
1 0
0 1
1
3 1 2 3

输出 #1

3

输入 #2

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
0 0
2 0
2 2
0 2
1 1
1
4 1 2 3 4

输出 #2

5

输入 #3

4 5
1 2
2 3
3 4
4 1
2 4
0 0
1 0
1 1
0 1
3
3 1 2 4
3 4 2 3
4 1 2 3 4

输出 #3

3
3
4