Chia nhóm giản đơn

Xem PDF

Điểm: 420 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một lớp học có \(n\) học sinh (\(n\) là bội của \(3\)), và giả sử rằng tất cả học sinh này được đánh số từ \(1\) đến \(n\).

Bây giờ, thầy chủ nhiệm muốn chia \(n\) học sinh này thành \(\frac{n}{3}\) nhóm, mỗi nhóm gồm \(3\) học sinh thoả mãn điều kiện sau:

  • Nếu học sinh thứ \(i\) muốn cùng nhóm với học sinh thứ \(j\) thì hai bạn \(i,j\) này phải cùng thuộc về một nhóm

  • Mỗi thí sinh chỉ thuộc về một nhóm duy nhất

Input

  • Dòng thứ nhất \(2\) số nguyên \(n,m(3\le n\le 48,0\le m\le \frac{n(n-1)}{2})\), trong đó \(n\) là số học sinh còn \(m\) là số cặp học sinh muốn cùng thuộc về một nhóm !

Output

  • Nếu không tồn tại cách chia nào thoả mãn in ra \(-1\), ngược lại in ra \(\frac{n}{3}\) dòng, mỗi dòng gồm \(3\) số nguyên thể hiện số thứ tự của các học sinh trong nhóm đó, ta có thể in ra theo thứ tự bất kì.

Example

Test 1

Input
6 3
1 2
2 3
3 4
Output
-1

Test 2

Input
3 2
1 2
2 3
Output
2 1 3

Bình luận