F. Bayan Testing
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Let us recall a well-known problem (also called a "bayan" in Russian). You are given an array $$$a_1, a_2, \ldots, a_n$$$ of integers. Answer the queries: given a segment $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$), check if there exist two equal elements among $$$a_l, a_{l+1}, \ldots, a_r$$$.

Please help to make good tests for this well-known problem! You are given two integers $$$n$$$, $$$m$$$, and also $$$2m$$$ different segments $$$[l_i, r_i]$$$. Find any array $$$a_1, a_2, \ldots, a_n$$$ such that, for exactly $$$m$$$ queries, the answer is positive, and for exactly $$$m$$$ queries, the answer is negative. You should report if there is no such array.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 10^5$$$).

Each of the next $$$2m$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — the given segments. It is guaranteed that all segments are different.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$m$$$ for all test cases does not exceed $$$10^5$$$.

Output

For each test case, print the answer to the problem.

If such an array $$$a$$$ exists, print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$). Otherwise, print a single integer $$$-1$$$.

If there are several possible answers, print any one of them.

Example
Input
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
Output
-1
1 2 3 3 2 1
5 5 5 5