복잡하게 얽힌 울타리

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

농부 John이 목장 사이의 울타리 $N$개를 모두 새로 배치하려고 한다 ($1 \le N \le 1000$). 각 울타리는 2차원 평면 위의 선분이다. 두 울타리는 오직 끝점에서만 만날 수 있으며, 모든 울타리는 자신의 두 끝점에서 각각 정확히 하나씩, 총 두 개의 다른 울타리와 만난다. 따라서 울타리들은 서로 겹치지 않는 하나 이상의 닫힌 다각형을 이룬다.

농부 John에게는 소 $C$마리가 있다 ($1 \le C \le 1000$). 각 소는 어떤 울타리 위에도 놓이지 않은 한 점에 서 있으며, 두 소가 같은 점에 있는 경우는 없다. 어떤 소가 울타리를 하나도 넘지 않고 다른 소가 있는 곳까지 걸어갈 수 있으면, 두 소는 같은 무리(community) 에 속한다.

가장 큰 무리에 속한 소의 수를 구하여라.

입력

  • 첫째 줄: 두 정수 $N$과 $C$가 공백으로 구분되어 주어진다.
  • 다음 $N$개의 줄: 각 줄에 정수 네 개 $x_1\ y_1\ x_2\ y_2$가 주어지며, $(x_1, y_1)$에서 $(x_2, y_2)$까지 이어지는 울타리를 뜻한다.
  • 그다음 $C$개의 줄: 각 줄에 정수 두 개 $x\ y$가 주어지며, 소 한 마리의 위치를 뜻한다.

모든 좌표는 0 이상 1,000,000 이하의 정수이다.

출력

  • 가장 큰 무리에 속한 소의 수를 한 줄에 출력한다.

힌트

울타리들이 닫힌 고리를 이루므로, 두 소는 자신들을 감싸는 고리의 집합이 완전히 같을 때에만 같은 무리에 속한다. 예제에서 울타리들은 하나의 정사각형과 그 안의 삼각형 두 개를 이루며, 네 마리 중 두 마리는 같은 고리 집합 안에 있어 같은 무리를 이루고 나머지 두 마리는 각자 혼자다.