E. Планарный граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Граф называется планарным, если он может быть изображен на плоскости так, что его ребра пересекаются только в вершинах.

Точкой сочленения называется такая вершина неориентированного графа, при удалении которой число компонент связности графа увеличивается.

Мостом называется такое ребро неориентированного графа, при удалении которого число компонент связности графа увеличивается.

Задан связный неориентированный планарный граф, состоящий из 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.

Гарантируется, что заданный граф не содержит мостов, точек сочленения, петель и кратных ребер. Гарантируется, что отрезки-ребра могут иметь общие точки только в вершинах графа.

Выходные данные

Для каждого запроса выведите единственное целое число — количество вершин внутри цикла, либо на нем самом. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных. Числа разделяйте пробельными символами.

Примеры
Входные данные
3 3
1 2
2 3
3 1
0 0
1 0
0 1
1
3 1 2 3
Выходные данные
3
Входные данные
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
Выходные данные
5
Входные данные
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
4