Bổn Sâm có ~n~ đồng xu khác nhau về trọng lượng và một cái cân hai bên. Mỗi khi anh ta đặt hai đồng xu ~x~ và ~y~ lên cân, trọng lượng tương đối giữa chúng sẽ được hiển thị — tức là anh ta biết được giữa ~x~ và ~y~, đồng nào nặng hơn.

Gọi cấp bậc của đồng xu ~x~ là số lượng đồng xu không nặng hơn đồng xu ~x~ (bao gồm cả chính nó). Do đó, đồng xu nhẹ nhất có cấp bậc là ~1~, đồng nhẹ nhì là ~2~, …, và đồng nặng nhất có cấp bậc là ~n~.

Sẽ có ~m~ lần cân. Với mỗi đồng xu, hãy xác định sau lần cân thứ ~m~ thì có thể chắc chắn biết cấp bậc của đồng xu đó.

Input

Dòng đầu tiên nhập hai số nguyên ~n, m~.

Tiếp theo là ~m~ dòng, dòng thứ ~i~ nhập hai số nguyên ~x, y~, cho biết kết quả lần cân thứ ~i~ là đồng xu ~x~ nặng hơn đồng xu ~y~.

Đảm bảo rằng các kết quả cân không mâu thuẫn với nhau.

Output

In ra một dòng gồm ~n~ số nguyên.

Số thứ ~i~ là lần cân sớm nhất sau đó có thể xác định chắc chắn cấp bậc của đồng xu ~i~.

Nếu không thể xác định, in -1 tại vị trí đó.

Scoring

Giới hạn dữ liệu

• ~2 \le n \le 200{,}000~

• ~1 \le m \le 800{,}000~

• ~1 \le x, y \le n,\ x \ne y~

Subtask

• Subtask 1 (6 điểm): ~n \le 7,\ m \le 20~

• Subtask 2 (16 điểm): ~n \le 100,\ m \le 400~

• Subtask 3 (10 điểm): ~n \le 1000,\ m \le 4000~

• Subtask 4 (68 điểm): không có ràng buộc gì thêm

Lưu ý

Trong mỗi subtask, nếu bạn chỉ xác định đúng rằng cấp bậc của từng đồng xu có thể hay không thể được xác định, nhưng không xác định đúng là được xác định sau lần cân thứ mấy, bạn vẫn sẽ nhận được 50% số điểm của subtask đó.

Sample Input 1

4 4
2 4
3 1
4 1
2 3

Sample Output 1

3 4 -1 -1

Sample Input 2

6 8
1 5
5 4
6 2
2 5
4 3
6 1
6 5
2 1

Sample Output 2

8 8 5 5 5 6

Notes

Giải thích ví dụ 1

Ta có thể xác định rằng sau 3 lần cân đầu tiên, đồng xu ~1~ là đồng xu nặng nhất, nhưng không thể biết điều đó chỉ sau 2 lần cân. Do đó, số nguyên đầu tiên trong kết quả đúng là ~3~.

Tương tự, ta có thể xác định rằng đồng xu ~2~ là đồng xu nhẹ nhất sau 4 lần cân, nhưng không phải sau 3 lần cân. Vì vậy, số nguyên thứ hai trong kết quả đúng là ~4~.

Lưu ý rằng cả hai thứ tự ~2,4,3,1~ và ~2,3,4,1~ đều là các cách sắp xếp hợp lệ của trọng lượng các đồng xu. Do đó, đồng xu ~3~ có thể có cấp bậc ~2~ hoặc ~3~, đều phù hợp với tất cả các kết quả cân, vì vậy cấp bậc của đồng xu ~3~ không bao giờ được xác định chắc chắn. Tương tự, đồng xu ~4~ cũng không bao giờ có cấp bậc xác định.

Nếu kết quả của bạn là 1 1 -1 -1, bạn sẽ đạt được 50% số điểm cho test nhỏ này.