Đồ Thị Ba Phần Đầy Đủ

Cho một đồ thị vô hướng đơn có $n$ đỉnh và $m$ cạnh. Đồ thị không chứa khuyên, giữa mỗi cặp đỉnh có nhiều nhất một cạnh, và có thể không liên thông.

Hãy chia $n$ đỉnh thành ba tập không rỗng $V_1,V_2,V_3$ (mỗi đỉnh thuộc đúng một tập) sao cho đồng thời:

1. Không có cạnh nào mà cả hai đầu mút cùng nằm trong một tập.
2. Với mọi cặp đỉnh $x,y$ ở hai tập khác nhau, tồn tại cạnh nối $x$ và $y$.

Nói cách khác, đồ thị đã cho phải trùng khớp với một đồ thị ba phần đầy đủ $K(|V_1|,|V_2|,|V_3|)$ nếu chọn được ba tập như trên.

Nếu tồn tại cách chia, in ra một cách bất kỳ. Nếu không, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ ($1\le a_i<b_i\le n$) mô tả một cạnh.

Dữ liệu ra

• Nếu tồn tại cách chia hợp lệ, in ra $n$ số nguyên, số thứ $i$ là chỉ số tập ($1$, $2$ hoặc $3$) mà đỉnh $i$ thuộc về. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
• Nếu không tồn tại, in ra $-1$.

Ràng buộc

• $3\le n\le {10}^5$
• $0\le m\le min(3·{10}^5,{\displaystyle \frac{n(n-1)}{2}})$

Ví dụ