Задача H. Три пути ≡

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии N городов и M дорог, по дорогам можно двигаться в обе стороны. Исторически сложилось, что каждый пингвин посещает ровно три города (возможно проезжая по пути через остальные города). Пингвины не любят однообразие, поэтому одна из самых популярных услуг в логистической компании это прокладка маршрутов между тремя городами a, b, c так чтобы при проезде из a в b, из a в c, и из b в с существовал максимум один город который посещался 3 раза.

Как вы уже могли догадаться Цапля просит вас о помощи, у неё скопилось ровно Q запросов вида a, b, c. И для каждого запроса требуется вывести 3 пути, из a в b, из a в c, и из b в c, так чтобы эти пути удовлетворяли заданным требованиям.

Формат входного файла

Входной файл содержит числа N и M. Далее следует M пар чисел u_i и v_i, означающих что города u_i и v_i соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел a_i, b_i, c_i.

Формат выходного файла

Выходной файл должен содержать 3 × Q строк, первое число в строке k_i — количество вершин в пути, далее k_i чисел — номера вершин пути в порядке посещения.

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ a_i, b_i, c_i ≤ N

Примеры тестов

3 2
1 2
2 3
1
1 2 3

2 1 2
3 1 2 3
2 2 3

4 3
1 2
1 3
1 4
2
3 4 1
1 2 4 

3 3 1 4 
2 3 1 
2 4 1 
2 1 2 
2 1 4 
3 2 1 4 

5 6
2 3
4 5
1 2
1 3
1 4
1 5
2
2 3 4
2 3 5

2 2 3 
3 2 1 4 
4 3 2 1 4 
2 2 3 
4 2 1 4 5 
5 3 2 1 4 5