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

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии 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 пар чисел ui и vi, означающих что города ui и vi соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел ai, bi, ci.

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

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

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ ui, vi ≤ N, ui ≠ vi, 1 ≤ ai, bi, ci ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
2 3
1
1 2 3
2 1 2
3 1 2 3
2 2 3
2
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 
3
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 

0.047s 0.011s 15