배송 서비스 timer 12s memory 2048MB

카스피 해 인근 여러 도시 사이의 배송 서비스를 시작하려는 인터시티 카스피안 패키지 회사(ICPC)는 택배를 운송할 배달원을 고용할 계획이다.

각 배달원은 집 도시와 목적지 도시를 가지며, 모든 배달원은 동일한 일정으로 이동한다. 9:00에 집 도시를 출발해 12:00에 목적지 도시 도착, 14:00에 목적지 도시 출발, 17:00에 집 도시로 복귀한다. 배달원이 집 도시나 목적지 도시 안에 있을 때는 고객에게서 물건을 받고 배송할 수 있다. 또한 같은 시간에 같은 도시 안에 있는 다른 배달원과 물건을 인계하거나 받을 수 있다. ICPC는 개인 서비스이므로, 물건은 창고 등에 보관되지 않는다 — 물건이 목적지에 도달하지 않는 한, 배달원은 (낮이든 밤이든) 항상 물건을 가지고 있거나 다른 배달원에게 넘겨야 한다.

회사는 어떤 물건이든 반드시 목적지로 전달될 수 있도록 배달원 간 인계 방식이 정해질 것이라고 기대한다. 두 도시 u와 v가 서로 연결되어 있다고 함은, 도시 u에서 v로, 그리고 v에서 u로 모두 배송이 가능한 경우를 말한다. 고용 과정의 효율을 측정하기 위해, 회사는 배달원이 한 명씩 고용될 때마다 연결된 도시 쌍 (u, v)의 개수(1 ≤ u < v ≤ n)를 알고 싶다.