Hãy cùng nhớ lại một bài toán nổi tiếng (còn được gọi là "bayan" trong tiếng Nga). Bạn được cho một mảng các số nguyên $a_1, a_2, \dots, a_n$. Hãy trả lời các truy vấn: cho một đoạn $[l, r]$ ($1 \le l \le r \le n$), kiểm tra xem có tồn tại hai phần tử bằng nhau trong đoạn $a_l, a_{l+1}, \dots, a_r$ hay không.

Hãy giúp tạo ra các bộ test tốt cho bài toán nổi tiếng này! Bạn được cho hai số nguyên $n, m$ và $2m$ đoạn $[l_i, r_i]$ khác nhau. Hãy tìm bất kỳ mảng $a_1, a_2, \dots, a_n$ nào sao cho có đúng $m$ truy vấn có câu trả lời là khẳng định (có tồn tại hai phần tử bằng nhau) và đúng $m$ truy vấn có câu trả lời là phủ định. Bạn cần thông báo nếu không tồn tại mảng như vậy.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^5$) — số lượng bộ test. Tiếp theo là mô tả các bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n, m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^5$).

Mỗi dòng trong $2m$ dòng tiếp theo chứa hai số nguyên $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — các đoạn đã cho. Đảm bảo rằng tất cả các đoạn đều khác nhau.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $2 \cdot 10^5$ và tổng của $m$ trên tất cả các bộ test không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ test, in ra câu trả lời cho bài toán.

Nếu tồn tại mảng $a$ như vậy, in ra $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). Nếu không, in ra một số nguyên duy nhất $-1$.

Nếu có nhiều đáp án khả thi, hãy in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1
1 2 3 3 2 1
5 5 5 5