VOI 18 Bài 2 - Dòng xe vào bến - VNOJ: VNOI Online Judge

VOI 18 Bài 2 - Dòng xe vào bến

Points: 1.00 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem type

Allowed languages

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

In case the statement didn't load correctly, you can download the statement here: Statement

Đọc đề gốc tại đây.

Bến xe khách liên tỉnh XYZ có ~M~ điểm đỗ đón xe khách cập bến để hành khách xuống xe. Các điểm đỗ được đánh số từ ~1~ đến ~M~. Ban điều hành bến xe nhận được yêu cầu cập bến của một dòng xe gồm ~N~ xe khách chờ được phục vụ cập bến, lần lượt xe này sau xe kia. Các xe khách được đánh số từ ~1~ đến ~N~ theo thứ tự chờ được phục vụ. Xe khách thứ ~i~ chỉ chấp nhận cập bến, nếu như nó được xếp phục vụ tại một trong số các điểm đỗ có chỉ số trong khoảng từ ~a_i~ đến ~b_i~ ~(1 \le a_i \le b_i \le M)~ và đồng thời tại điểm đỗ được bố trí để phục vụ nó chưa có xe nào trong số các xe (trong dòng xe đang xét) đến trước đã cập bến tại đó. Nếu có một xe khách đến lượt được phục vụ mà Ban điều hành không tìm được điểm đỗ theo đúng yêu cầu để phục vụ nó, thì xe này và tất cả các xe đến sau nó sẽ đồng loạt di chuyển sang bến xe khác và việc phục vụ dòng xe chấm dứt tại đây.

Yêu cầu: Hãy giúp Ban điều hành bến xe xác định số lượng lớn nhất các xe khách trong dòng xe mà bến xe khách XYZ có thể phục vụ đáp ứng các điều kiện đã nêu.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 5)~ là số lượng test. Tiếp đến là ~T~ nhóm dòng, mỗi nhóm là thông tin về một test theo khuôn dạng sau đây:

Dòng đầu tiên chứa hai số nguyên ~M~ và ~N~ tương ứng là số lượng điểm đỗ trong bến xe và số lượng xe trong dòng xe yêu cầu được phục vụ;
Dòng thứ ~i~ trong số ~N~ dòng tiếp theo mô tả yêu cầu của xe khách thứ ~i~ gồm hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i \le b_i \le M)~ mô tả khoảng chỉ số của các điểm đỗ trong bến xe mà xe khách thứ ~i~ chấp nhận được phục vụ tại đó. Hai số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra ~T~ dòng, mỗi dòng ghi số lượng xe khách lớn nhất trong dòng xe mà bến xe khách XYZ có thể phục vụ là câu trả lời cho test tương ứng trong dữ liệu vào.

Giới hạn

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 10~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 300~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 50\,000; \; a_i = 1, \; i = 1, 2, \ldots, N~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 50\,000~.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Note

Giải thích: Trong ví dụ thứ nhất, xe khách thứ nhất yêu cầu được cập bến ở một trong các điểm đỗ ~1, 2, 3, 4~, ta có thể xếp nó vào điểm đỗ số ~4~. Cả hai xe khách ~2~ và ~3~ đều yêu cầu được cập bến ở điểm đỗ số ~1~, do đó, không thể phục vụ được xe khách số ~3~ (đến sau).

Trong ví dụ thứ hai, hai xe khách đầu tiên có thể xếp với điểm đỗ số ~1~ và ~2~ (xe ~1~ vào điểm đỗ số ~1~ và xe ~2~ vào điểm đỗ số ~2~, hoặc xe ~1~ vào điểm đỗ số ~2~ và xe ~2~ vào điểm đỗ số ~1)~. Xe khách thứ ba phải xếp cập bến tại điểm đỗ số ~3~. Đến lượt xe khách thứ tư, ta không tìm được điểm đỗ nào đáp ứng yêu cầu của nó, vì thế bến xe XYZ chấm dứt phục vụ dòng xe tại đây, mặc dù nếu bỏ qua xe khách thứ tư, ta có thể xếp điểm đỗ cho xe khách số ~5~ (nhưng xe này và cả xe khách số ~6~ đã theo xe khách số ~4~ đi tìm bến xe khác).

Comments

Please read the guidelines before commenting.

There are no comments at the moment.