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

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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) \leq 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 \leq T \leq 50 000$
$2 \leq n \leq 10^{5}$
$1 \leq l_{i} \leq r_{i} \leq 2 \cdot 10^{5}$
Tổng $n$ trên tất cả truy vấn không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
3 2 5 5 2 3 3 3 5 2 3 2 3 3 3 3 4 4 5 5	2 1 -1 1 2 2	Truy vấn 1: hai đoạn rời nhau, mỗi đoạn vào một nhóm. Truy vấn 2: đoạn $[3, 5]$ cắt cả $[2, 3]$ và $[2, 3]$ , nên cả ba phải cùng nhóm $\Rightarrow$ không thể có hai nhóm khác rỗng. Truy vấn 3: ba đoạn rời nhau hoàn toàn — chia tuỳ ý miễn cả hai nhóm khác rỗng.
2 4 1 5 2 3 10 12 11 11 2 1 10 5 6	1 1 2 2 -1	Truy vấn 1: nhóm thành phần liên thông ${[1, 5], [2, 3]}$ và ${[10, 12], [11, 11]}$ . Truy vấn 2: đoạn $[5, 6]$ nằm trong $[1, 10]$ $\Rightarrow$ chỉ một thành phần.

Bình luận

Không có bình luận tại thời điểm này.