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

Замок Чудовища состоит из $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$ чисел --- номера вершин. Если подходящих циклов несколько, можно вывести любой из них.