В чемпионатах по спортивной «Своей игре» часто используется схема проведения финала, называемая «супердевятка». В ней для девяти участников составляют список боёв по три человека, такой что каждый участник оказывается в одном бою с каждым другим участником ровно один раз.
Участники занумерованы числами от 1 до 9. Вам даётся несколько боёв (троек чисел от 1 до 9), требуется построить минимальную по числу боёв супердевятку, в которой есть все эти бои, или определить, что такой супердевятки не бывает.
Первая строка содержит одно целое число $$$n$$$ — число заданных боёв ($$$0 \le n \le 84$$$).
Каждая из последующих $$$n$$$ строк содержит по три различных целых числа от 1 до 9 — номера участников соответствующего боя. Гарантируется, что для любых двух боёв есть участник, который участвует в одном из этих боёв и не участвует в другом.
Если решения не существует, выведите $$$-1$$$. Иначе в первой строке выведите число $$$k$$$ — наименьшее число боёв, которое необходимо добавить, а в следующих $$$k$$$ строках по три целых числа — номера участников в $$$i$$$-м из дополняющих боёв. Если решений несколько, выведите любое.
3 1 2 3 1 3 4 6 7 8
-1
12 3 2 8 3 9 4 6 7 2 6 8 9 7 1 9 8 1 5 4 7 8 1 6 3 2 1 4 6 4 5 3 5 7 5 9 2
0
0
12 3 2 8 3 9 4 6 7 2 6 8 9 7 1 9 8 1 5 4 7 8 1 6 3 2 1 4 6 4 5 3 5 7 5 9 2