B. Програмчлалын багш

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Програмчлалын хичээлийн багш $n$ тооны сурагчдад хичээл заадаг. Бүх сурагчид $1$-ээс $n$ хүртэл дугаарлагдсан бөгөөд $n$ нь $3$-т хуваагддаг тоо байна.

Сургуулийн програмчлалын тэмцээн болохын өмнө багш сурагчдыг $3$, $3$-н хүнтэй баг болгон хуваахаар шийджээ. Зарим сурагчид хамт нэг багт орохыг хүсч байлаа. Үүнээс гадна хэрвээ $i$ дэхь сурагч $j$ дэхь сурагчтай нэг багт орохыг хүсч байвал $j$ дэхь сурагч мөн адил $i$ дэхь сурагчтай нэг багт орохыг хүсч байгаа. Багш багуудыг тэмцээнд сайн оролцоосой гэж хүсч байгаа учир нэг багт орохыг хүссэн сурагчдын хүсэлтийг бүгдийг нь биелүүлэхээр шийджээ. Гэхдээ сурагч бүр зөвхөн нэг л багт харьяалагдах ёстой.

Багшид туслан түүний хүссэнээр багуудыг хуваарилахад туслаарай.

Оролт

Эхний мөрөнд хоёр ширхэг бүхэл тоо $n$, $m$ $(3 ≤ n ≤ 48;$ $0 \leq m \leq \frac{n(n-1)}{2})$ өгөгдөнө. Дараагийн $m$ ширхэг мөрөнд мөр бүрд нэг багт орохыг хүсэж буй хоёр сурагчийн дугаар $a_{i}, b_{i}$ $(1 ≤ a_{i} < b_{i} ≤ n)$ өгөгдөнө.

$n$ нь ямаг $3$-т хуваагдах бөгөөд $a_{i}, b_{i}$ хоёр тоо нь оролтонд хамгийн ихдээ $1$ удаа орсон байна.

Гаралт

Хэрвээ нөхцлүүдийг хангахаар багуудыг хуваарилах боломжгүй бол "-1" гэж хэвлэнэ үү. Харин олдож байвал $\frac{n}{3}$ мөрөнд $i$ дэхь багийн сурагчдын дугаар болох $x_{i}$, $y_{i}$, $z_{i}$ $(1 ≤ x_{i}, y_{i}, z_{i} ≤ n)$ тоонуудыг хэвлэнэ үү.

Хэрвээ нэгээс олон хариулт олдвол аль нэгийг нь хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
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 
Сэтгэгдлүүдийг ачааллаж байна...