Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) đến \(n\). Tìm một dãy \(a\) gồm \(n\) số nguyên không âm thỏa mãn điều kiện sau:

Với mọi đỉnh \(u\) từ \(1\) đến \(n\), gọi \(v_1, ..., v_k\) là các đỉnh có cạnh nối trực tiếp với \(u\), ta có: \(a_u = MEX([a_{v_1}, a_{v_2}, ..., a_{v_k}])\)

Trong đó, MEX của một dãy \(b\) là giá trị nguyên không âm nhỏ nhất mà không tồn tại trong dãy \(b\). Ví dụ:

• \(MEX([2, 2, 1]) = 0\)
• \(MEX([3, 1, 0, 1]) = 2\)
• \(MEX([0, 3, 1, 2]) = 4\)

Nếu không tồn tại bất kỳ dãy \(a\) nào thỏa mãn điều kiện trên, in ra \(-1\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le min(n(n-1)/2, 10^5)\)) - số đỉnh và số cạnh của đồ thị.
• \(m\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(u_i\), \(v_i\) (\(1 \le u_i, v_i \le n\), \(u_i ≠ v_i\)) - biểu diễn cạnh thứ \(i\) của đồ thị.

Output

• Nếu không tồn tại dãy \(a\) thỏa mãn yêu cầu, in ra \(-1\).
• Ngược lại, in ra \(n\) số nguyên không âm là \(a_1, a_2, ..., a_n\), mỗi số cách nhau bởi một dấu cách.

Examples

Input

5 5
1 3
1 2
2 4
2 3
3 5

Output

0 1 2 0 0

Input

5 4
1 2
2 4
4 5
1 3

Output

0 1 1 0 1

Ghi chú

Một đồ thị được gọi là đồ thị hai phía nếu tồn tại một cách tô màu các đỉnh bằng hai màu (xanh và đỏ) sao cho với mọi cạnh \((u, v)\), hai đỉnh \(u\) và \(v\) có màu khác nhau.

Scoring

• Subtask 1 (2%): \(m = n - 1\), \(u_i = i\), \(v_i = i + 1\).
• Subtask 2 (8%): \(m = n - 1\), và đồ thị liên thông.

• Subtask 3 (20%): \(n ≥ 100\). Đồ thị thỏa mãn:

  • Không có cạnh nào có cả hai đỉnh lớn hơn \(n - 20\)
  • Nếu loại bỏ các đỉnh \(n, n - 1, ..., n - 19\) và các cạnh liên quan thì đồ thị còn lại là đồ thị hai phía
• Subtask 4 (10%): Với mọi cạnh \((u_i, v_i)\), ta có \(-2 \le v_i - u_i \le 2\)
• Subtask 5 (60%): Không có điều kiện gì thêm