Красавица и циклы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
loopquery.in
вывод
loopquery.out

Замок Чудовища состоит из n комнат, которые пронумерованы от 1 до n. Они соединены коридорами — между каждой парой различных комнат проходит ровно один коридор. Влюбившись в Красавицу, Чудовище подарило ей некоторые коридоры. Таким образом, каждый коридор принадлежит либо Красавице, либо Чудовищу.

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

Красавица хочет подробно изучить замок. Она выбрала q пар чисел li, ri. Для каждой из них она хочет найти цикл, такой что:

Для каждой пары чисел выведите такой цикл или сообщите, что его нет.

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

В первой строке входных данных заданы два числа — количество комнат в замке n и количество коридоров, которые принадлежат Красавице m (1 ≤ n ≤ 105, ).

В следующих m строках описаны коридоры Красавицы. В i-й из них записаны числа ai и bi, которые означают, что коридор между комнатами ai и bi принадлежит Красавице (1 ≤ ai, bi ≤ n, ai ≠ bi). Ни один коридор не встречается среди этих строк более одного раза. Все остальные коридоры принадлежат Чудовищу.

В следующей строке записано число q (1 ≤ q ≤ 105).

В следующих q строках записан пары li, ri (1 ≤ li ≤ ri ≤ n).

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

Выведите q строк. В i-й строке выведите ответ для i-й пары:

Система оценки

Первая группа тестов состоит из тестов, для которых выполняются ограничения n, m, q ≤ 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.

Вторая группа тестов состоит из тестов, для которых выполняются ограничения n, m ≤ 105, q = 1. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.

Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 60 баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Запросить информацию о проверке» на вкладке «Решения».

Пример

Входные данные
5 5
1 2
2 3
3 4
4 5
5 1
2
1 5
1 4
Выходные данные
5 4 2 5 3 1
-1