Золотые драконы — это бессмертные величественные создания, с начала времён населяющие Энию. Всего в Энии живёт n золотых драконов, каждый в своём собственном гнезде. Проблема состоит в том, что некоторые пары драконов недолюбливают друг друга, а некоторые пары гнёзд расположены настолько близко друг к другу, что если прорычать в одном из них, то в другом будет прекрасно слышно. Однако у каждого дракона не более a врагов, а у каждого гнезда не более b соседних с ним гнёзд. Также известно, что n ≥ 3ab.
Драконам надоело слышать рычание своих неприятелей, и они решили переселиться так, чтобы каждый дракон занимал ровно одно гнездо, и никакие два враждующих дракона не жили в соседних гнёздах.
В первой строке содержится единственное целое число n (1 ≤ n ≤ 5000) — количество драконов.
Во второй строке содержится единственное целое число m (
) — количество пар враждующих драконов. Далее m строк содержат по два целых числа через пробел: xj и yj (1 ≤ xj < yj ≤ n) — пару номеров враждующих драконов. Гарантируется, что каждая пара встречается только один раз.
В следующей строке содержится единственное целое число k (
) — количество пар соседних гнёзд. Далее k строк содержат по два целых числа через пробел: pj и qj (1 ≤ pj < qj ≤ n) — пару номеров соседних гнёзд. Гарантируется, что каждая пара встречается только один раз.
В первой строке выведите «Solution exists» без кавычек, если существует вариант расселения драконов, удовлетворяющий условию задачи, иначе выведите «Wrong answer» без кавычек.
В первом случае во второй строке выведите n целых чисел di через пробел, где di — это номер дракона, которому следует поселиться в i-ом гнезде. Если существует несколько ответов, выведите любой из них.
3
1
1 2
1
1 3
Solution exists
2 1 3
4
2
1 2
3 4
2
1 3
2 4
Solution exists
1 2 3 4
