CF223E.Planar Graph

A graph is called planar, if it can be drawn in such a way that its edges intersect only at their vertexes.

An articulation point is such a vertex of an undirected graph, that when removed increases the number of connected components of the graph.

A bridge is such an edge of an undirected graph, that when removed increases the number of connected components of the graph.

You've got a connected undirected planar graph consisting of n vertexes, numbered from 1 to n, drawn on the plane. The graph has no bridges, articulation points, loops and multiple edges. You are also given q queries. Each query is a cycle in the graph. The query response is the number of graph vertexes, which (if you draw a graph and the cycle on the plane) are located either inside the cycle, or on it. Write a program that, given the graph and the queries, will answer each query.

若一个图可以画在平面上，使得其任意两条边仅在端点处相交，则称该图为平面图（planar graph）。

割点（articulation point）是指无向图中的一个顶点，当将其移除后，图的连通分量数目会增加。

桥边（bridge）是指无向图中的一条边，当将其移除后，图的连通分量数目会增加。

现给定一个包含 $n$ 个顶点（编号为 $1$ 至 $n$）的连通无向平面图，该图已绘制在平面上。图中不含桥边、割点、自环及重边。此外还给出 $q$ 个查询，每个查询对应图中的一个环。对于每个查询，要求输出：当将该图及其所给环一同绘制在平面上时，位于该环内部或环上的图的顶点总数。请编写程序，在给定图和所有查询的前提下，对每个查询给出答案。

The first line contains two space-separated integers n and m (3 ≤ n, m ≤ 105) — the number of vertexes and edges of the graph. Next m lines contain the edges of the graph: the i-th line contains two space-separated integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — the numbers of vertexes, connecting the i-th edge. The next n lines contain the positions of the planar graph vertexes on the plane: the i-th line contains a pair of space-separated integers x__i and y__i (|x__i|, |y__i| ≤ 109) — the coordinates of the i-th vertex of the graph on the plane.

The next line contains integer q (1 ≤ q ≤ 105) — the number of queries. Then follow q lines that describe the queries: the i-th line contains the sequence of space-separated integers k__i, _a_1, _a_2, ..., a__k__i (1 ≤ a__j ≤ n; k__i > 2), where k__i is the cycle length in the i-th query, a__j are numbers of the vertexes that form a cycle. The numbers of vertexes in the cycle are given in the clockwise or counterclockwise order. The given cycles are simple, that is they cannot go through a graph vertex more than once. The total length of all cycles in all queries does not exceed 105.

It is guaranteed that the given graph contains no bridges, articulation points, loops and multiple edges. It is guaranteed that the edge segments can have common points only at the graph's vertexes.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$3 \leq n, m \leq 10^5$）—— 分别表示图的顶点数和边数。接下来的 $m$ 行描述图的边：第 $i$ 行包含两个以空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$）—— 表示第 $i$ 条边所连接的两个顶点的编号。随后的 $n$ 行给出该平面图各顶点在平面上的位置：第 $i$ 行包含一对以空格分隔的整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10^9$）—— 表示图中第 $i$ 个顶点在平面上的坐标。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 表示查询的数量。随后是 $q$ 行，每行描述一个查询：第 $i$ 行包含一串以空格分隔的整数 $k_i, a_1, a_2, \dots, a_{k_i}$（其中 $1 \leq a_j \leq n$，且 $k_i > 2$），其中 $k_i$ 表示第 $i$ 个查询中环的长度，$a_j$ 表示构成该环的顶点编号。环中顶点的编号按顺时针或逆时针顺序给出。所给的环均为简单环，即不会重复经过图中的任一顶点。所有查询中各环的总长度不超过 $10^5$。

保证所给图中不含桥边、割点、自环及重边；保证任意两条边的线段仅可能在图的顶点处相交。

For each query print a single integer — the number of vertexes inside the cycle or on it. Print the answers in the order, in which the queries follow in the input. Separate the numbers by spaces.

对于每个查询，输出一个整数——位于环内或环上的顶点数量。按输入中查询出现的顺序输出答案。各数字之间用空格分隔。