CF223E Planar Graph

如果一个图可以被绘制在平面上，并且仅在顶点处有公共点，那么称该图为平面图。 割点是无向图中的一个顶点，移除它会导致图的连通分量数量增加。 桥是一条无向图中的边，移除它会导致图的连通分量数量增加。 你有一个连通的无向平面图，该图包含 $n$ 个编号为 $1$ 到 $n$ 的顶点，且已经在平面上绘制。该图没有桥、割点、自环和重边。 接下来你会收到 $q$ 个询问。每个询问给你一个在图中的环。对于每个询问，请你回答该环上以及环内部共有多少个顶点。（即在平面上绘制出该环后，有多少个顶点位于该环上或环内部。）请编写程序，给定图和所有询问，依次输出每个询问的答案。

第一行包含两个用空格分隔的整数 $n$ 和 $m$（$3 \leq n,m \leq 10^{5}$），分别表示图中的顶点数和边数。 接下来 $m$ 行，每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条边连接的顶点编号。 接下来 $n$ 行，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10^{9}$），表示第 $i$ 个顶点在平面上的坐标。 下一行包含整数 $q$（$1 \leq q \leq 10^{5}$），表示询问的数量。 接下来 $q$ 行，每行描述一个询问：首先一个整数 $k_i$，然后是 $k_i$ 个整数 $a_1, a_2, \ldots, a_{k_i}$（$1 \leq a_j \leq n; k_i > 2$），表示组成该环的顶点编号。环上的顶点编号按照顺时针或逆时针给出。所有给定的环都是简单环，即不会经过某个顶点多次。所有询问中所有环的长度总和不超过 $10^5$。 保证给定的图没有桥、割点、自环和重边。保证边段只有在顶点处才能有公共点。

对于每个询问，输出一个整数，表示环上或环内部的顶点数量。按输入顺序输出答案，数之间用空格分隔。

由 ChatGPT 5 翻译