Красавица и циклы

Замок Чудовища состоит из $n$ комнат, которые пронумерованы от $1$ до $n$. Они соединены $\displaystyle\frac{n\cdot (n-1)}{2}$ коридорами --- между каждой парой различных комнат проходит ровно один коридор. Влюбившись в Красавицу, Чудовище подарило ей некоторые коридоры. Таким образом, каждый коридор принадлежит либо Красавице, либо Чудовищу.

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

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

• все комнаты в этом цикле имеют номер от $l\_i$ до $r\_i$ включительно,
• количество комнат в цикле не больше $100$,
• либо все коридоры в цикле принадлежат Красавице, либо все коридоры в цикле принадлежат Чудовищу.

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

В первой строке входных данных заданы два числа --- количество комнат в замке $n$ и количество коридоров, которые принадлежат Красавице $m$ ($1 \leq n \leq 10^5$, $0 \leq m \leq min(10^5, \displaystyle\frac{n\cdot(n-1)}{2}$).

В следующих $m$ строках описаны коридоры Красавицы. В $i$-й из них записаны числа $a\_i$ и $b\_i$, которые означают, что коридор между комнатами $a\_i$ и $b\_i$ принадлежит Красавице ($1\leq a\_i,b\_i \leq n$, $a\_i \neq b\_i$). Ни один коридор не встречается среди этих строк более одного раза. Все остальные коридоры принадлежат Чудовищу.

В следующей строке записано число $q$ ($1 \leq q \leq 10^5$).

В следующих $q$ строках записан пары $l\_i$, $r\_i$ ($1 \leq l\_i \leq r\_i \leq n$).

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

• Если подходящего цикла не существует, выведите $-1$.
• Если цикл есть, выведите $k\_i$ --- длину цикла, а затем $k\_i$ чисел --- номера вершин. Если подходящих циклов несколько, можно вывести любой из них.