부족전쟁 Output Only Compilation commands

2014년 12월 25일, 드디어 부족전쟁 1세계의 막이 내렸습니다. 그 장대한 서사시는 대하소설로 써도 모자람이 없지만, 그것도 과거의 일, 최근에는 몇십 명 정도의 거대 유저들만이 남아 게임을 떠난 유저들의 마을들을 흡수해나갈 뿐이었습니다.

마지막 날 유저 NanaPanzer는 과거의 추억에 잠겨 자신의 오천여 개 마을들을 바라보다가, 다음과 같은 생각을 했습니다.

• '이 마을들을 모두 먹는 데에 참 시간이 오래 걸렸지. 수십명의 유저들이 격렬히 저항했고, 이 마을들을 모두 손에 넣기까지는 무려 7년이나 지났어. 이 마을들이 원래부터 주인이 없는 마을들이었다면 어땠을까?' (유저 NanaPanzer의 마지막 말)

NanaPanzer는 시간이 훨씬 적게 걸렸을 것으로 생각은 했지만, 정확하게 얼마나 걸렸을지는 어림잡기도 힘들었습니다. 이제 부족을 잊고 쉬려고 하는 NanaPanzer를 위해서, 이 궁금증을 해결해줍시다.

필수 정보

마을은 총 $n$개 있으며, 각 마을에는 1 이상 $n$ 이하의 자연수 번호가 붙어 있습니다. $i$번 마을은 2차원 평면 위의 점 $(X_{i}, Y_{i})$로 나타낼 수 있습니다. 한 점에는 많아야 한 마을만 있을 수 있습니다. 1번 마을은 "시작 마을"이라고 불리는데, 게임을 처음 시작할 때 자신이 소유하고 있는 유일한 마을입니다.

시작 마을에서는 5시간에 1번씩 귀족이 생산됩니다. 생산된 귀족은 자신의 소유가 아닌 임의의 마을로 가서, 그 마을의 영주로 군림하여, 자신의 소유로 만들 수 있습니다. 이렇게 해서 소유하게 된 마을들에서도 5시간에 1번씩 귀족이 생산됩니다. 만약 생산된 귀족이 다른 마을로 떠나지 않는다면, 이 귀족은 자동으로 사라지고, 이 귀족을 생산한 마을에서는 더 이상 귀족이 생산되지 않습니다.

어떤 귀족이 마을 $A$에서 마을 $B$로 가는 데 걸리는 시간은 분입니다.

해야 할 일

NanaPanzer가 모든 마을을 자신의 소유로 만드는 데에 걸리는 시간을 최소화해주세요. 이를 위해 여러분은 귀족들이 어느 마을로 이동할지를 결정해야 합니다.

입력 형식

첫 번째 줄에는 마을의 수 $n$이 주어집니다.

이후 $n$개 줄이 주어지는데, 이 중 $i$번째 줄 ($1 \le i \le n$)에는 두 개의 정수 $X_{i}$와 $Y_{i}$가 공백을 사이로 두고 주어집니다. 이것은 $(X_{i}, Y_{i})$가 $i$번 마을의 좌표임을 의미합니다.

위에서 언급했듯이, 입력으로 주어진 1번 마을이 시작 마을이며, 좌표가 겹치는 마을은 없습니다.

출력 형식

총 $n$줄을 출력합니다. $i$번째 줄 ($1 \le i \le n$)에는 처음에 $i$번 마을에서 생산된 귀족의 수를 출력하고, 그 다음부터 시간 순서대로 귀족이 어느 마을로 떠났는지를 공백을 사이로 두고 출력합니다.

파일 정보

각 입력 파일은 모두 부족전쟁 1세계의 실제 유저 데이터이며, 각 데이터의 유저 아이디와 $n$, 기준시간의 값은 다음과 같습니다. 입력 파일은 e_input.zip에서 내려받을 수 있습니다.

입력 파일명	출력 파일명	유저 아이디	n	기준 시간 S
E1.in	E1.out	일루일루이	305	8,100
E2.in	E2.out	바람	2,675	10,700
E3.in	E3.out	bismark77	2,919	12,200
E4.in	E4.out	NanaPanzer	5,269	15,700
E5.in	E5.out	이동꾸옹	11,022	16,800

채점 방식

각 출력 파일에 대한 여러분의 점수는 아래와 같이 계산됩니다.

• 만약 여러분의 계획이 문제에서 제시한 조건을 만족하지 않는다면 0점입니다.
• 만약 여러분의 계획이 문제에서 제시한 조건을 만족한다면, 다음과 같이 점수가 계산됩니다. 기준시간을 $S$, 여러분이 모든 마을을 정복하는 데 들인 시간을 $Y$로 둡시다.

• $S < Y$이면 점.
• $S \ge Y$이면 점.

제출한 답안의 점수는 각 출력 파일에서 받은 점수들의 합이 됩니다.

예제

입력

4
0 0
0 10
10 0
10 10

출력

3 4 2 3
0
0
0

총 걸리는 시간은 1250분입니다.