Chia đoạn thành hai nhóm

Cho $n$ đoạn thẳng $[l_i,r_i]$ trên trục số. Bạn cần chia toàn bộ các đoạn này thành hai nhóm khác rỗng sao cho không tồn tại cặp đoạn thuộc hai nhóm khác nhau mà có ít nhất một điểm chung. Hai đoạn $[a,b]$ và $[c,d]$ được coi là có điểm chung nếu $max(a,c)\le min(b,d)$ — bao gồm cả trường hợp chỉ chạm đầu mút như $[1,5]$ và $[5,10]$. Mỗi đoạn phải thuộc đúng một trong hai nhóm.

Hãy in ra một cách phân chia hợp lệ, hoặc thông báo rằng không tồn tại cách phân chia.

Để giảm áp lực dữ liệu, mỗi file kiểm thử chứa nhiều truy vấn độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$ — số truy vấn.
• Mỗi truy vấn được mô tả như sau:
  • Dòng đầu chứa số nguyên $n$ — số đoạn.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i,r_i$ — đoạn thứ $i$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng:

• Nếu không tồn tại cách phân chia hợp lệ, in $-1$.
• Ngược lại, in $n$ số nguyên $t_1,t_2,\dots ,t_n$ ($t_i\in \{1,2\}$), trong đó $t_i$ là chỉ số nhóm của đoạn thứ $i$. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le T\le 50000$
• $2\le n\le {10}^5$
• $1\le l_i\le r_i\le 2·{10}^5$
• Tổng $n$ trên tất cả truy vấn không vượt quá ${10}^5$.

Ví dụ