최소 신장 트리

$G$는 연결된 가중 무방향 그래프이다. $G$의 신장 트리(spanning tree) $T$는 (1) 트리이면서 (2) $G$의 모든 정점을 연결하는 부분 그래프이다. 신장 트리의 가중치는 그 트리에 속한 간선들의 가중치 합이다. 최소 신장 트리(minimum spanning tree)는 다른 모든 신장 트리보다 가중치가 작거나 같은 신장 트리이다.

주어진 트리 $T$가 주어진 그래프 $G$의 최소 신장 트리인지 판별하는 프로그램을 작성하시오.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스에서는 그래프 $G$와 검사할 트리들이 주어진다.

각 테스트 케이스의 첫 줄에는 $G$의 정점 수를 나타내는 정수 $n$ ($1 < n \le 1000$)이 주어진다. 정점은 $1$번부터 $n$번까지 번호가 매겨진다.

이어지는 $n-1$개의 줄에는 가중치 인접 행렬의 상삼각 부분이 다음과 같이 주어진다.

W(1,2) W(1,3) ... W(1,n-1) W(1,n)
W(2,3) W(2,4) ... W(2,n)
...
W(n-1,n)

여기서 $W_{i,j}$ ($0 \le W_{i,j} \le 1000$)는 정점 $i$와 $j$ 사이 간선의 가중치이며, $W_{i,j} = 0$은 두 정점 사이에 간선이 없음을 뜻한다.

행렬 다음 줄에는 이 그래프에 대해 검사할 트리의 개수 $Q$ ($0 < Q \le 1000$)가 주어진다.

이어서 주어지는 $Q$개의 트리는 각각 정점 번호 하나로 된 단일 정점이거나, 다음 형식으로 표현된다.

(R T1 T2 ... Tc)

여기서 $R$은 루트 정점의 번호이고, $T_1, \dots, T_c$ ($0 < c \le 1000$)는 $R$의 부분 트리로 같은 방식으로 재귀적으로 표현된다.

입력의 끝은 $n$ 자리에 $0$ 하나만 있는 줄로 표시된다.

각 트리마다 다음 형식으로 한 줄씩 출력한다.

a.b result

여기서 $a$는 테스트 케이스 번호($1$부터 시작), $b$는 해당 테스트 케이스 안에서의 트리 번호($1$부터 시작)이며, result는 그 트리가 $G$의 최소 신장 트리이면 YES, 아니면 NO이다. $b$와 result 사이에는 공백 하나를 두고, 줄 끝에 불필요한 공백을 남기지 않는다.