Jabber 네트워크

Dave는 은퇴 후에도 지역 커뮤니티의 컴퓨터 네트워크를 계속 관리하는 옛 컴퓨터 과학 교수이다. 구성원마다 컴퓨터가 한 대씩 있고, 각 컴퓨터에는 네트워크 카드가 세 개씩 있다. 일부 카드는 케이블로 연결되어 있다. 네트워크는 하나로 이어져 있으며, 자원을 아끼는 오랜 관례에 따라 케이블 수는 가능한 한 적게 유지된다.

구성원들의 통신 습관은 꾸준하다. 임의의 두 컴퓨터 사이에 초당 주고받는 패킷 수는 정확히 알려져 있다. 다만 네트워크는 오래전에 구축되었으므로 지금의 연결이 최적이라고 할 수 없다. 두 컴퓨터 $i$, $j$에 대해 $d_{ij}$는 케이블 수로 잰 두 컴퓨터 사이의 최단 경로 길이이고, $c_{ij}$는 $i$에서 $j$로 초당 전송해야 하는 패킷 수이다. 통신 부하(commutation stress)는 $i < j$인 모든 쌍에 대해 $c_{ij} \cdot d_{ij}$를 더한 값이며, Dave는 이 값을 최소로 만들고자 한다.

케이블이 낡아 이제 교체할 때가 되었다. Dave는 이 기회에 통신 부하가 줄어들도록 네트워크도 함께 개선하려 한다. 다만 한꺼번에 많이 바꾸면 구성원들이 불편을 겪을 수 있으므로, 다음 절차로 작업한다. 기존 케이블을 입력 순서대로 하나씩 처리하며, 각 케이블마다 다음을 수행한다.

1. 기존 케이블 하나를 제거한다.
2. 네트워크가 다시 연결되도록 새 케이블 하나를 추가한다. 이때 결과의 통신 부하가 최소가 되도록 연결할 두 컴퓨터를 고른다.
3. 같은 통신 부하를 만드는 선택이 여럿이면 번호가 작은 쪽을 고른다. 즉 $(u_1, u_2)$와 $(v_1, v_2)$의 통신 부하가 같을 때, $u_1 < v_1$이거나 $u_1 = v_1$이고 $u_2 < v_2$이면 $(u_1, u_2)$를 택한다.

각 컴퓨터의 네트워크 카드는 세 개뿐이므로, 이미 세 대와 연결된 컴퓨터에는 케이블을 하나 더 연결할 수 없다. 그래도 연결할 두 컴퓨터는 항상 찾을 수 있다. 예를 들어 방금 분리된 두 컴퓨터를 고를 수 있다.

변경 전	기존 케이블 제거 후	새 케이블 추가 후

그림 J.1: 재연결 한 번의 과정 (첫 번째 작업)

첫 줄에 정수 $n$ $(2 \le n \le 2 \cdot 10^3)$이 주어진다. 컴퓨터의 수이다.

다음 $n-1$개 줄에는 각각 정수 $a_i$, $b_i$ $(1 \le a_i < b_i \le n)$가 주어진다. 이는 $i$번째 기존 케이블이 연결한 두 컴퓨터이다. 케이블은 입력 순서대로 제거되고 교체된다. 기존 케이블만으로 모든 컴퓨터가 서로 연결되어 있으며, 어떤 컴퓨터도 세 대보다 많은 컴퓨터와 연결되어 있지 않다.

다음 줄에는 정수 $d$ $(2 \le d \le 10^4)$가 주어진다. 서로 데이터를 주고받는 컴퓨터 쌍의 수이다. 다음 $d$개 줄에는 각각 정수 $s_i$, $t_i$, $d_i$ $(1 \le s_i < t_i \le n,\ 1 \le d_i \le 10^9)$가 주어진다. $s_i$와 $t_i$는 서로 데이터를 주고받는 두 컴퓨터이고, $d_i$는 초당 패킷 수이다.

$n-1$개 줄을 출력한다. $i$번째 줄에는 $i$단계에서 새 케이블로 연결한 두 컴퓨터 $x_i$, $y_i$ $(1 \le x_i < y_i \le n)$를 출력한다. 동점을 깨는 규칙 때문에 정답은 하나로 정해진다.