如果一个图可以以其边仅在顶点相交的方式绘制,则该图被称为平面图。
关节点是无向图的顶点,当移除该顶点时,图的连通分量的数量会增加。
桥是无向图的边,当被移除时,图的连接组件的数量会增加。
你有一个连通的无向平面图,由 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