울타리 설계

당신은 울타리 건설 회사의 임시 직원으로 고용되어 들판의 울타리 설계를 마무리하는 일을 맡았다. 각 울타리는 두 기둥 사이를 직선으로 이어야 한다. 각 기둥은 한 점을 차지하며 기둥의 위치는 고정되어 있다. 세 기둥이 한 직선 위에 있는 경우는 없다. 울타리끼리는 끝점(기둥)에서만 만날 수 있고, 그 외에는 교차할 수 없다.

다른 사람이 설계를 시작했지만 울타리 두 개를 추가한 뒤 그만두었다. 당신은 그 설계를 마무리해야 한다. 상사와 고객에게 좋은 인상을 주기 위해, 울타리 길이와 상관없이 최대한 많은 울타리를 만들고 싶다.

기둥의 위치와 이미 만들어진 울타리가 주어질 때, 어떤 울타리 쌍(새로 추가한 것과 기존 것 모두)도 끝점(기둥)에서만 만나고 그 외에는 교차하지 않도록 울타리를 최대한 많이 추가하는 방법을 구하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 뒤따른다. 각 테스트 케이스는 기둥의 수를 나타내는 정수 N 하나가 있는 줄로 시작한다. 그 다음 N개의 줄이 주어진다. 이 중 i번째 줄에는 i번째 기둥의 위치를 나타내는 두 정수 Xi와 Yi가 주어진다. 각 테스트 케이스의 마지막 두 줄은 이미 만들어진 두 울타리를 나타낸다. 이 두 줄에는 각각 두 정수 Pk와 Qk가 주어지며, 이는 k번째 기존 울타리가 Pk번째 기둥과 Qk번째 기둥을 잇는다는 뜻이다(기둥은 1부터 번호가 매겨진다).

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 설계에 추가할 수 있는 울타리의 최대 개수(기존 울타리는 포함하지 않음)이다. 그 다음 y개의 줄을 출력한다. 각 줄에는 서로 다른 두 정수 i와 j(둘 다 1 이상 N 이하)가 있어야 하며, 이는 i번째 기둥과 j번째 기둥을 잇는 서로 다른 울타리 하나를 나타낸다. y+2개의 울타리(기존 울타리와 추가한 울타리 모두) 중 어떤 쌍도 끝점(기둥)에서만 만나고 그 외에는 겹치지 않아야 한다.

• 1 ≤ T ≤ 10.
• 모든 i에 대해 −109 ≤ Xi ≤ 109.
• 모든 i에 대해 −109 ≤ Yi ≤ 109.
• i ≠ j인 모든 i, j에 대해 (Xi, Yi) ≠ (Xj, Yj).
• 모든 k에 대해 1 ≤ Pk < Qk ≤ N.
• 기존 울타리는 끝점에서만 만나고 그 외에는 교차하지 않는다.
• 세 기둥이 한 직선 위에 있는 경우는 없다.

다음 그림은 주어진 예제의 기둥과 울타리를 나타낸다. 굵은 파란 선이 그어진 울타리가 기존 울타리이고, 나머지는 예제 출력에 나온 대로 울타리를 최대한 많이 추가한 방법을 나타낸다.