계획적인 정원사

Jackstraw Gardening Club은 공동으로 소유한 땅을 나누어 쓰는 원예가들의 협동조합이다. 클럽은 매년 이 땅을 회원들에게 나누어 주며, 각 회원은 넓은 땅 안에서 자기만의 구획을 받는다.

매년 겨울 식재 시기 전에 클럽 회원들은 땅에 모여 구획을 고른다. 회원은 각자 나무 말뚝 몇 개와 실타래 하나를 가지고 있다. 회원들은 돌아가며 한 명씩 새 말뚝을 땅에 박을 수 있고, 그다음 한 쌍 이상의 말뚝 사이에 실을 묶어 두 점을 직선으로 잇는다. 실끼리는 교차할 수 없고(같은 말뚝에 묶인 끝점에서의 만남은 예외), 같은 직선 위에 겹쳐 놓을 수도 없다. 실의 양 끝을 같은 말뚝에 묶을 수는 없다. 말뚝은 기존의 실이나 말뚝에 너무 가까워서 그 사이를 쉽게 넘어갈 수 없게 박을 수 없다.

실로 완전히 둘러싸인 땅의 각 부분이 하나의 텃밭 구획이 된다. 회원 과반수가 충분한 수의 닫힌 구획이 만들어졌다고 느끼고 멈추기로 할 때까지 이 과정은 계속된다. 단, 다음 조건을 따른다.

• 멈출 때 쓸모없는 실은 모두 제거된다. 쓸모없는 실이란 그 실의 양쪽 땅이 같은 구획에 속하거나, 닫히지 않은 땅 쪽에 속하는 실이다.
• 쓸모없는 실을 제거한 뒤에도 닫힌 영역이 하나 이상 남아 있어야 한다.
• 넓이가 0인 닫힌 구획은 있을 수 없다.
• 쓸모없는 실을 제거하고 남은 실은 모두 연결되어 있어야 한다. 땅 안의 어떤 실에서 다른 어떤 실로든 실을 따라 갈 수 있는 경로가 있어야 한다.

그 뒤 원예가들은 닫힌 영역 가운데에서 자기 구획을 고른다.

당신은 운 좋게도 첫 번째로 고를 권한을 가졌다. 다른 원예가 대부분은 얻을 수 있는 가장 넓은 구획을 노릴 것이 분명하지만, 당신의 목표는 완전히 다르다. 다음 군 품평회에서 1등을 차지할 호박 한 덩이를 키우고 싶다. 넓은 공간은 필요 없지만, 사슴, 토끼, 쥐 같은 네 발 달린 야생동물이 호박을 갉아 먹을까 걱정된다. 해충이 당신의 구획에 닿기 전에 다른 구획을 최대한 많이 건너야 하는 구획을 고르고 싶다. 다른 원예가들이 기르는 다양한 작물이 해충의 주의를 흩뜨려 당신의 구획에 도달하기 전에 발길을 돌리게 하기를 바란다. 해충은 말뚝 위나 바로 위를 밟지 않고, 항상 말뚝의 한쪽을 지나간다.

입력은 하나 이상의 데이터셋으로 이루어진다. 각 데이터셋은 정수 두 개 $P$, $E$가 적힌 줄로 시작하며, $2 < P \leq 750$, $3 \leq E \leq 1000$이다. $P$가 0이면 입력이 끝난다.

데이터셋의 첫 줄 다음에는 $P$개의 줄이 오며, 각 줄에는 한 점의 $x,y$ 좌표가 있다. 좌표는 0 이상 10000 이하의 정수이고, 점들은 서로 다르다.

그 줄들 다음에는 $E$개의 줄이 오며, 각 줄에는 두 점을 잇는 점 번호 한 쌍이 있다. 점 번호는 0부터 $P-1$까지이며, 입력에 주어진 점의 순서를 가리킨다. 점 0은 처음 주어진 점이다.

각 데이터셋에 대해, 바깥에서 다가오는 동물이 선택한 구획에 도달하기 전에 가로질러야 하는 다른 구획 수의 최솟값을 최대로 만드는 구획을 찾아라. 선택한 구획에 대해 그 동물이 가로질러야 하는 다른 구획 수의 최솟값을 출력하라.

입력 예시에는 데이터셋이 두 개 있다. "0 14" 줄로 끝나는 첫 번째 데이터셋은 위의 그림에 해당한다. 그림에서 음영 처리된 구획이 계획적인 원예가가 고른 구획이다.