광기의 과학도시 자운에는 10억 개의 가로 도로와 10억 개의 세로 도로가 있다. 당신은 편의상 각 가로 도로와 세로 도로에 각각 순서대로 1~10억의 번호를 매기고, A번 가로 도로와 B번 세로 도로가 만나는 교차로를 (A, B)라고 정했다. 이웃한 두 도로 사이의 거리는 같기 때문에, 이웃한 두 도로 사이를 평범한 방법으로 이동한다면 도달 시간은 1로 일정하다.

신지드가 당신에게 화학 물질 배달을 의뢰하였다. 각 의뢰마다, (P, Q)에 있는 화학 물질을 (R, S)로 옮겨야 한다. 매 의뢰마다, 신지드는 당신을 (P, Q)로 바로 보내기 때문에 (P, Q)로 가는 데 걸리는 시간은 무시해도 좋다.

당신은 N개의 비밀 통로에 대해서 출입을 허가받았다. 각 비밀 통로는 (Pk, Qk)와 (Rk, Sk)를 연결하는데, 이 비밀 통로를 이용해서 두 지점 사이를 자유롭게 왕래가능하고, 이 때 1의 시간이 걸린다. 화학 물질을 빨리 배달하지 않으면 그 화학 물질에 중독될 수 있기 때문에, 가능한 빨리 배달하려고 한다. 신지드의 각 의뢰에 대해서 그 의뢰를 수행할 때 걸리는 최소 시간을 구하는 프로그램을 작성하여라. 단, 한 교차로에 두 개 이상의 비밀 통로가 있을 수 있다.

#2719 upload 31 done 7 how_to_reg 7

의뢰 (Request) timer 1s memory 128MB

#2719

의뢰 (Request) 1s 128MB