| Codeforces Round 181 (Div. 2) |
|---|
| Закончено |
У тренера по программированию есть n обучающихся у него студентов, причем известно, что n делится на 3. Пускай все студенты пронумерованы от 1 до n, включительно.
Тренер хочет перед чемпионатом университета по программированию разделить всех студентов на команды из трех человек. Для некоторых пар студентов известно, что они хотят быть в одной команде. Причем, если i-ый студент хочет быть в команде с j-ым, то и j-ый хочет быть в команде с i-ым. Тренер заинтересован в том, чтобы команды показали хороший результат, поэтому он хочет, чтобы было выполнено условие: если i-ый студент хочет быть в одной команде с j-ым, то i-ый и j-ый студенты должны быть в одной команде. Также, очевидно, каждый студент должен быть ровно в одной команде.
Помогите тренеру, разделите команды так, как он хочет.
В первой строке входных данных записаны целые числа n и m (3 ≤ n ≤ 48, 
. Далее следует m строк, в каждой из них записана пара целых чисел ai, bi (1 ≤ ai < bi ≤ n) — пара ai, bi означает, что студенты с номерами ai и bi хотят быть в одной команде.
Гарантируется, что n делится на 3. Гарантируется, что каждая пара ai, bi упоминается во входных данных не более одного раза.
Если искомого разбиения на команды не существует, выведите число -1. Иначе выведите 
строки. В каждой строке выведите три целых числа xi, yi, zi (1 ≤ xi, yi, zi ≤ n) — i-ая команда.
Если существует несколько ответов, разрешается вывести любой.
3 0
3 2 1
6 4
1 2
2 3
3 4
5 6
-1
3 3
1 2
2 3
1 3
3 2 1
