교차점 개수

직사각형의 네 변 위에 여러 점이 놓여 있습니다. 같은 모양의 점은 정확히 두 개씩 있으며, 꼭짓점에 놓인 점은 없습니다. 각 모양마다 두 점을 직사각형 내부만 지나는 직선 또는 곡선으로 연결하려고 합니다. 연결선끼리는 서로 교차할 수 있지만, 세 개 이상의 연결선이 한 점에서 만나면 안 됩니다.

가능한 연결 방법 중 전체 교차점 수를 최소로 만들 때의 교차점 수를 구하세요. 또한 그렇게 최소로 만든 그림에서, 하나의 연결선이 가질 수 있는 교차점 수의 최댓값도 구하세요.

점은 (s, d) 형태로 나타냅니다. s가 1이면 윗변, 2이면 아랫변, 3이면 왼쪽 변, 4이면 오른쪽 변입니다. 점이 윗변이나 아랫변에 있으면 d는 왼쪽 꼭짓점부터의 거리이고, 왼쪽 변이나 오른쪽 변에 있으면 위쪽 꼭짓점부터의 거리입니다.

첫 줄에 점의 개수 N이 주어집니다. N은 50을 넘지 않습니다. 같은 모양의 점은 두 개씩 있으므로, 다음 N / 2개의 줄에는 같은 모양인 두 점의 위치가 한 줄에 하나씩 주어집니다.

각 줄에는 네 정수 s1 d1 s2 d2가 주어지며, 이는 두 점 (s1, d1)과 (s2, d2)를 뜻합니다. 주어진 점의 위치는 모두 서로 다릅니다. 모든 수는 양의 정수이고, 거리 값은 50을 넘지 않습니다.

첫 줄에 가능한 최소 전체 교차점 수를 출력합니다.

둘째 줄에 전체 교차점 수가 최소가 되도록 연결했을 때, 하나의 연결선이 갖는 교차점 수의 최댓값을 출력합니다.