Thảo luậnSnackDown Online Pre-elimination round A - Protecting The Poison

Vương quốc của các con rắn là một lưới N*N. Sở hữu có giá trị nhất của chúng là bộ sưu tập chất độc được chứa trong lưới K*K. Dữ liệu đảm bảo rằng N và K là số lẻ. “Trung tâm” được định nghĩa như sau: trong lưới N*N, (i, j) thể hiện ô ở hàng thứ i và cột thứ j và (1, 1) là ô góc trái trên và (N, N) là ô góc phải dưới. Chất độc được chứa ở hình vuông K*K với góc trái trên là ( (N - K)/2 + 1, (N - K)/2 + 1 ).

Nhưng có những tên trộm muốn đánh cắp chất độc. Chúng không thể đi vào lưới N*N, nhưng chúng lại có thể bắn tên từ bên ngoài. Những mũi tên đi theo một hàng ngang (từ trái qua phải hoặc từ phải qua trái) hoặc đi theo một hàng dọc (từ trên xuống dưới hoặc từ dưới lên trên). Nếu mũi tên trúng lưới K*K, một số chất độc sẽ dính vào mũi tên và nếu mũi tên đó ra khỏi lưới N*N sau đó, những tên trộm sẽ cướp chất độc thành công.

Vì là vua của các con rắn, bạn muốn ngăn chặn nỗ lực của bọn trộm. Bạn biết các mũi tên sẽ gãy và dừng lại nếu chạm vào vảy trên da rắn nhưng lại ko làm đau các con rắn. Có một số con rắn đang bảo vệ chất độc. Mỗi con rắn chiếm một số ô liên tục trên một đường thẳng trong lưới N*N. Tức là chúng nằm trên một hàng hoặc một cột. Chú ý rằng các con rắn có thể giao nhau. Một cách sắp xếp các con rắn là “an toàn” nếu bọn trộm không thể lấy cắp chất độc. Nghĩa là nếu bắn tên từ bất kỳ hàng hoặc cột nào thì hoặc mỗi tên sẽ trúng một con rắn và dừng lại (điều này có thể xảy ra ngay cả khi nó vừa thoát khỏi lưới K*K) hoặc nó không đi vào lưới K*K.

Nhà vua có một nhiệm vụ khác cho các con rắn. Bởi vì muốn bỏ càng nhiều rắn ra khỏi cách sắp xếp càng tốt miễn sao cách sắp xếp còn lại vẫn là “an toàn”. Hãy giúp anh ta tìm ra số lượng rắn nhỏ nhất cần giữ lại để bảo vệ chất độc.

Dữ liệu vào

- Dòng đầu tiên chứa một số nguyên T là số lượng test

- Dòng đầu của mỗi test chứa ba số nguyên: N, K và M với N là kích thước của lưới hình vuông, K là kích thước của lưới hình vuông chứa độc và M là số con rắn ban đầu.

- Trong M dòng tiếp theo, dòng thứ i chứa 4 số nguyên HXi, HYi, TXi, TYi. (HXi, HYi) là ô chứa đầu con rắn thứ i. (TXi, TYi) là ô chứa đuôi con rắn thứ i. Dữ liệu đảm bảo rằng hai ô đó cùng nằm trên một hàng hoặc cùng nằm trên một cột. Và những ô ở giữa chúng, bảo gồm cả hai ô đó thể hiện con rắn thứ i.

Dữ liệu ra

- Với mỗi test, in ra một số nguyên trên một dòng: số rắn nhỏ nhất cần giữ lại để bảo vệ chất độc. Nếu không thể bảo vệ chất độc ngay cả khi có tất cả các con rắn, in ra -1.

Ràng buộc

- 1 ≤ T ≤ 4

- 3 ≤ N ≤ 10^9

- 1 ≤ K ≤ N-2

- Cả N và K đều là số lẻ

- 1 ≤ M ≤ 10^5

- 1 ≤ HXi, HYi, TXi, TYi ≤ N

- Dữ liệu đảm bảo (HXi = TXi) hoặc (HYi = TYi) với mọi i

- Không có ô nào trong lưới K*K chứa rắn

Ví dụ

Input:

2
7 3 7
1 1 6 1
1 2 3 2
5 2 5 2
2 4 2 6
6 2 6 4
5 6 5 7
7 1 7 4
7 3 7
1 1 6 1
1 2 3 2
5 2 5 2
2 6 2 6
6 2 6 4
5 6 5 7
7 1 7 4

Output:

3
-1

Giải thích

Ví dụ đầu tiên tương ứng với

Chú ý rằng ô trái trên của lưới N*N là (1, 1). Hình vuông bên trong chứa độc và 7 con rắn được vẽ mỗi con một màu. Con rắn màu xanh lá cây là con rắn đầu tiên trong input.

Chúng ta có thể bỏ 3 con rắn mà vẫn có thể bảo vệ chất độc. Một cách sắp xếp là

Bạn có thể thấy không có mũi tên nào có thể vào ô hình vuông bên trong và ra khỏi hình vuông bên ngoài mà không bị đâm vào con rắn. Do đó nó an toàn. Và bạn không thể bảo vệ nếu dùng số rắn ít hơn. Do đó 3 là đáp án

Ví dụ thứ hai tương ứng với Bạn có thể kiểm tra kể cả dùng tất cả các con rắn, đó vẫn không là cách sắp xếp an toàn, bởi các tên trộm có thể bắn một mũi tên xuống cột thứ 5 và lấy cắp chất độc. Do đó đáp án là -1.