벌 정원

조지의 아버지 벤은 양봉을 좋아한다. 그는 시골 별장 근처에 벌 정원을 가지고 있으며, 정원을 거닐면서 벌집에서 꿀을 모으는 것을 즐긴다.

벤의 정원에는 여러 지점에 놓인 $n$개의 벌집이 있다. 일부 벌집들은 서로, 또는 벤의 집과 곧은 길로 연결되어 있다. 벤은 항상 길을 따라서만 걷고, 한 길에서 다른 길로 갈아타는 일은 오직 벌집에서만 일어난다. 벤의 집과 모든 벌집은 어떤 길 위에도 놓여 있지 않다.

길들은 집에서 임의의 벌집까지 가는 경로가 정확히 하나만 존재하도록 배치되어 있다. 즉, 집과 $n$개의 벌집은 길에 의해 하나의 트리를 이룬다.

벤은 매주 왕복 산책을 한다. 집에서 출발하여 길을 따라 걸으며 모든 벌집을 적어도 한 번씩 방문한 뒤 집으로 돌아오는데, 항상 이러한 경로 중 가장 짧은 것을 택한다.

나이 든 아버지의 수고를 덜어 드리기 위해, 조지는 곧은 길 하나를 새로 놓아 이 왕복 경로를 가능한 한 짧게 만들려고 한다. 새 길은 두 벌집을 잇거나, 하나의 벌집과 벤의 집을 이어야 한다. 기존 길과 마찬가지로 벤의 집이나 어떤 벌집도 새 길 위에 놓여서는 안 된다. 어떤 길을 놓아야 하는지 구하여라.

첫째 줄에 벌집의 수 $n$이 주어진다 ($1 \le n \le 200$).

정원을 좌표평면 위에 놓고 벤의 집을 점 $(0, 0)$에 둔다. 이어지는 $n$개의 줄에는 각각 두 정수, 즉 한 벌집의 좌표가 주어진다. 모든 좌표의 절댓값은 $10^4$ 이하이며, 서로 같은 위치의 벌집은 없고, $(0, 0)$에 놓인 벌집도 없다. 벌집에는 $1$번부터 $n$번까지 번호가 매겨져 있다.

그다음 $n$개의 줄에는 각 기존 길이 잇는 두 지점의 번호가 주어진다. 이때 $0$은 벤의 집을, $1$부터 $n$까지는 벌집을 나타낸다.

주간 왕복 경로를 가장 많이 줄여 주는 새 곧은 길 하나에 대해, 그 길이 잇는 두 지점의 번호를 출력한다. 벤의 집은 $0$, 벌집은 $1$부터 $n$까지의 번호로 나타내며, 더 작은 번호를 먼저 하여 두 수를 공백 하나로 구분해 출력한다.

왕복 경로를 같은 최대량만큼 줄이는 서로 다른 길이 여러 개라면, 그중 사전순으로 가장 앞서는 쌍을 출력한다(첫 번째 수를 먼저 비교하고, 같으면 두 번째 수를 비교한다).

왕복 경로를 줄일 수 있는 곧은 길이 하나도 없다면 -1을 출력한다.