Sau khi ghé thăm một bảo tàng nghệ thuật hiện đại, Farmer John quyết định thiết kế lại trang trại bằng cách di chuyển toàn bộ \(N\) (\(1 \le N \le 1000\)) hàng rào giữa các đồng cỏ! Mỗi hàng rào được mô tả bởi một đoạn thẳng trên mặt phẳng hai chiều. Nếu hai hàng rào gặp nhau thì chúng chỉ gặp tại các đầu mút. Mỗi hàng rào chạm đúng hai hàng rào khác, một hàng rào tại mỗi đầu mút.

FJ có \(C\) con bò (\(1 \le C \le 1000\)) trong trang trại. Mỗi con bò ở tại một điểm trên mặt phẳng hai chiều không nằm trên bất kỳ hàng rào nào, và không có hai con bò nào ở cùng một điểm. Hai con bò được xem là thuộc cùng một cộng đồng nếu một con có thể đi đến con kia mà không chạm vào bất kỳ hàng rào nào. Hãy giúp FJ xác định số lượng bò trong cộng đồng lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một hàng rào từ điểm \((x_1, y_1)\) đến điểm \((x_2, y_2)\). Mọi tọa độ đều là số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\).
• \(C\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\), mô tả vị trí của một con bò. Mọi tọa độ đều là số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\).

Dữ liệu ra

In ra số lượng bò trong cộng đồng lớn nhất.

Ví dụ

10 4
0 0 10 0
10 0 10 10
0 0 0 10
10 10 0 10
8 8 9 8
9 8 8 9
8 9 8 8
2 7 3 2
3 2 7 5
7 5 2 7
15 3
1 4
4 5
7 1

2

Nguồn

USACO 2012 December Contest, Silver — Problem 1: Crazy Fences

Tác giả đề: Brian Dean, 2012.