Замок Чудовища состоит из n комнат, которые пронумерованы от 1 до n. Они соединены 
коридорами — между каждой парой различных комнат проходит ровно один коридор. Влюбившись в Красавицу, Чудовище подарило ей некоторые коридоры. Таким образом, каждый коридор принадлежит либо Красавице, либо Чудовищу.
Цикл — это путь по комнатам, который начинается и заканчивается в одной комнате и не проходит ни по одному коридору и ни через одну комнату больше одного раза, при этом количество комнат в цикле больше 1.
Красавица хочет подробно изучить замок. Она выбрала q пар чисел li, ri. Для каждой из них она хочет найти цикл, такой что:
- все комнаты в этом цикле имеют номер от li до ri включительно,
- количество комнат в цикле не больше 100,
- либо все коридоры в цикле принадлежат Красавице, либо все коридоры в цикле принадлежат Чудовищу.
В первой строке входных данных заданы два числа — количество комнат в замке 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-й пары:
- Если подходящего цикла не существует, выведите - 1.
- Если цикл есть, выведите ki — длину цикла, а затем ki чисел — номера вершин. Если подходящих циклов несколько, можно вывести любой из них.
Первая группа тестов состоит из тестов, для которых выполняются ограничения 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