Граф называется планарным, если он может быть изображен на плоскости так, что его ребра пересекаются только в вершинах.
Точкой сочленения называется такая вершина неориентированного графа, при удалении которой число компонент связности графа увеличивается.
Мостом называется такое ребро неориентированного графа, при удалении которого число компонент связности графа увеличивается.
Задан связный неориентированный планарный граф, состоящий из n вершин, пронумерованных от 1 до n, уложенный на плоскость. Граф не имеет мостов, точек сочленения, петель и кратных ребер. Также заданы q запросов. Каждый запрос представляет из себя цикл в графе. Ответ на запрос — количество вершин графа, которые (если нарисовать граф и цикл на плоскости) находятся внутри цикла, либо на нем самом. Напишите программу, которая по заданному графу и запросам отвечает на каждый из запросов.
Выходные данные
Для каждого запроса выведите единственное целое число — количество вершин внутри цикла, либо на нем самом. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных. Числа разделяйте пробельными символами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
2 3
3 1
0 0
1 0
0 1
1
3 1 2 3
|
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
|
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
4
|