시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 1 1 50.000%

문제

Given graph G which is a connected, weighted, undirected graph, a spanning tree T is a subgraph of G which is: (1) a tree that (2) connects all the vertices of G together. The weight of a spanning tree is the sum of the weights of the edges in that tree. A minimum spanning tree is a spanning tree: (3) whose weight is less than or equal to the weight of every other spanning tree.

Write a program that determines if a given tree T is a Minimum Spanning Tree for a given graph G.

입력

Your program will be tested on one or more test cases. For each test case you’ll be given a graph G and one or more trees to test. The first line of a test case will have a single positive integer n denoting the number of vertices in G (where 1 < n ≤ 1000). The vertices are numbered starting from 1. The next (n − 1) lines specify the upper triangle of the graph’s adjacency matrix as seen here:

W1,2 W1,3 . . . W1,n−1 W1,n 
W2,3 W2,4 . . . W2,n
.
.
.
Wn−1,n

where Wi,j is the weight of the edge between vertices i and j. Wi,j = 0 iff there is no edge between i and j. Note that 0≤ Wi,j ≤1000

Following the graph specification, a test case will specify a single positive number Q on a separate line where 0 < Q ≤ 1000. Q denotes the number of trees to test on the given graph. 

Each tree either consists of a single vertex, given by its number, or is specified as:

(R T1 T...Tc)

where R is the number of the vertex at the root and T1,...,Tc (where 0 < c ≤ 1000) are the sub-trees of R specified recursively.

The last line of the input file will have a single zero.

출력

For each query, write the result on a separate line using the following format:

a.b.␣result

where a is the test case number (starting at 1,) and b is the query number within this test case (again starting at 1.) result is either "YES" or "NO" indicating if the tree is a minimum spanning tree or not.

예제 입력

6 
2  6 11 0 0 
0 10  0 0 
0  0  7 
3  4 
5 
3 
(6 (3 (1 2)) (4 5)) 
(3 (1 2) (6 (4 5))) 
(4 1 2 5 6) 
5
 6 6  0 6 
 6 0 10 
10 6 
10 
2 
(1 2 5 (3 4)) 
(5 4 (3 2 1)) 
0

예제 출력

1.1 YES 
1.2 YES 
1.3 NO 
2.1 YES 
2.2 YES

힌트