Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
AP  Art Plagiarism 
You have pictures of two sculptures. The sculptures consist of several solid metal spheres, and some rubber pipes connecting pairs of spheres. The pipes in each sculpture are connected in such a way that for any pair of spheres, there is exactly one path following a series of pipes (without repeating any) between those two spheres. All the spheres have the same radius, and all the pipes have the same length.
You suspect that the smaller of the two sculptures was actually created by simply removing some spheres and pipes from the larger one. You want to write a program to test if this is possible.
The input will contain several test cases. One sculpture is described by numbering the spheres
consecutively from 1, and listing the pairs of spheres which are connected by pipes. The
numbering is chosen independently for each sculpture.
Input
One line containing an integer C, the number of test cases in the input file.
For each test case, there will be:
• One line containing the integer N, the number of spheres in the large sculpture.
• N−1 lines, each containing a pair of spaceseparated integers, indicating that the two
spheres with those numbers in the large sculpture are connected by a pipe.
• One line containing the integer M, the number of spheres in the small sculpture.
• M−1 lines, each containing a pair of spaceseparated integers, indicating that the two
spheres with those numbers in the small sculpture are connected by a pipe.
Output
C lines, one for each test case in the order they occur in the input file, containing:
• "Case #X: YES" if the small sculpture in case X could have been created from the large
sculpture in case X
• "Case #X: NO" if it could not. (X is the number of the test case, between 1 and C.)
Limits
1 <= C <= 50
2 <= N <= 50
1 <= M <= N
Sample input
2
5
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
5
1 2
1 3
1 4
4 5
4
1 2
2 3
3 4
Sample output
Case #1: NO
Case #2: YES
Được gửi lên bởi:  sieunhan 
Ngày:  20091129 
Thời gian chạy:  0.100s1s 
Giới hạn mã nguồn:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Ngôn ngữ cho phép:  Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET 
Nguồn bài:  Google Code Jam  ACM Vietnam Practice 
hide comments
20160924 15:45:37
Code AC: http://shink.in/lyAND 

20120513 05:16:54 T7
N<=50 hay N<=100 ? : 