Przypomnijmy sobie dobrze znany problem (w języku rosyjskim nazywany również „bayan”). Dana jest tablica liczb całkowitych $a_1, a_2, \dots, a_n$. Odpowiedz na zapytania: dla danego przedziału $[l, r]$ ($1 \le l \le r \le n$), sprawdź, czy wśród elementów $a_l, a_{l+1}, \dots, a_r$ istnieją dwa równe.

Pomóż przygotować dobre testy do tego znanego problemu! Dane są dwie liczby całkowite $n, m$ oraz $2m$ różnych przedziałów $[l_i, r_i]$. Znajdź dowolną tablicę $a_1, a_2, \dots, a_n$ taką, aby dla dokładnie $m$ zapytań odpowiedź była twierdząca, a dla dokładnie $m$ zapytań odpowiedź była przecząca. Jeśli taka tablica nie istnieje, zgłoś to.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^5$) — liczbę zestawów danych. Następnie opisane są zestawy danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $n, m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^5$).

Każda z kolejnych $2m$ linii zawiera dwie liczby całkowite $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — podane przedziały. Gwarantuje się, że wszystkie przedziały są różne.

Gwarantuje się, że suma $n$ dla wszystkich zestawów danych nie przekracza $2 \cdot 10^5$, a suma $m$ dla wszystkich zestawów danych nie przekracza $10^5$.

Wyjście

Dla każdego zestawu danych wypisz odpowiedź na problem.

Jeśli taka tablica $a$ istnieje, wypisz $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). W przeciwnym razie wypisz pojedynczą liczbę $-1$.

Jeśli istnieje kilka możliwych odpowiedzi, wypisz dowolną z nich.

Przykład

Wejście 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

Wyjście 1

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