현대 미술 표절

조각상 두 개를 찍은 사진이 있다. 조각상은 속이 꽉 찬 금속 공 여러 개와, 공 두 개를 잇는 고무 파이프 몇 개로 이루어진다. 파이프는 어떤 두 공을 골라도 같은 파이프를 두 번 지나지 않고 두 공을 잇는 경로가 정확히 하나만 있도록 연결되어 있다. 공의 반지름은 모두 같고, 파이프의 길이도 모두 같다.

당신은 두 조각상 중 작은 쪽이 큰 쪽에서 공과 파이프를 몇 개 떼어내 만든 것이라고 의심한다. 큰 조각상에서 공과 파이프를 떼어낸 뒤 남은 부분이 연결 구조까지 작은 조각상과 똑같아질 수 있는지 판정하는 프로그램을 작성하라. 공 번호는 두 조각상에서 따로 매기므로 번호가 아니라 모양만 일치하면 된다.

입력에는 테스트 케이스가 여러 개 들어 있다. 한 조각상은 공에 1부터 차례로 번호를 붙이고 파이프로 이어진 공 번호의 쌍을 나열해서 나타낸다.

첫째 줄에 입력 파일에 들어 있는 테스트 케이스의 개수 $C$가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 큰 조각상의 공 개수 $N$이 주어진다.
• 다음 $N-1$개 줄에 공백으로 구분된 정수 두 개가 주어진다. 큰 조각상에서 그 번호의 공 두 개가 파이프로 이어져 있다는 뜻이다.
• 다음 줄에 작은 조각상의 공 개수 $M$이 주어진다.
• 다음 $M-1$개 줄에 공백으로 구분된 정수 두 개가 주어진다. 작은 조각상에서 그 번호의 공 두 개가 파이프로 이어져 있다는 뜻이다.

제한

• $1 \le C \le 50$
• $2 \le N \le 100$
• $1 \le M < N$

입력에 주어진 순서대로 테스트 케이스마다 한 줄씩, 모두 $C$개 줄을 출력한다. $X$번째 테스트 케이스에서 작은 조각상을 큰 조각상에서 만들어낼 수 있으면 Case #X: YES를, 만들어낼 수 없으면 Case #X: NO를 출력한다. 여기서 $X$는 1 이상 $C$ 이하인 테스트 케이스 번호이고, # 다음에는 그 번호를 그대로 쓴다.

예제의 첫 번째 테스트 케이스에서 큰 조각상은 공 다섯 개가 일렬로 이어진 모양이고, 작은 조각상은 공 하나에 다른 공 세 개가 붙은 모양이다. 큰 조각상에서 무엇을 떼어내도 이 모양은 나오지 않는다.

두 번째 테스트 케이스에서 작은 조각상은 공 네 개가 일렬로 이어진 모양이다. 작은 조각상의 공을 큰 조각상의 2, 1, 4, 5번 공에 순서대로 대응시키면 된다.