만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

현대 미술 표절 (작은 입력)

면접 대비

시간 제한5초메모리 제한512 MB

요약
작은 나무가 큰 나무의 연결된 부분그래프인지 판정한다. 번호는 무시하고 모양만 따진다.
난이도

쉬움10점 중 3점

유형
트리, 백트래킹
정답자
아직 제출이 없습니다

문제

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

둘 중 작은 조각상이 큰 조각상에서 구와 파이프를 몇 개 떼어내 만든 것이라고 의심하고 있다. 그렇게 만드는 것이 가능한지 판정하는 프로그램을 작성한다.

조각상은 구에 1부터 차례로 번호를 붙이고 파이프로 이어진 구의 쌍을 나열해서 나타낸다. 번호는 두 조각상에 각각 따로 붙이므로, 같은 번호가 같은 구를 뜻하지는 않는다. 입력에는 테스트 케이스가 여러 개 들어 있다.

입력

첫째 줄에 테스트 케이스의 수 CC가 주어진다.

각 테스트 케이스는 다음 순서로 주어진다.

  • 한 줄에 큰 조각상의 구 개수 NN
  • N−1N-1개의 줄, 각 줄에 공백으로 구분된 두 정수. 큰 조각상에서 그 두 번호의 구가 파이프로 이어져 있다는 뜻이다.
  • 한 줄에 작은 조각상의 구 개수 MM
  • M−1M-1개의 줄, 각 줄에 공백으로 구분된 두 정수. 작은 조각상에서 그 두 번호의 구가 파이프로 이어져 있다는 뜻이다.

제한

  • 1≤C≤1001 \le C \le 100
  • 2≤N≤82 \le N \le 8
  • 1≤M<N1 \le M < N

출력

테스트 케이스마다 한 줄씩, 입력에 주어진 순서대로 CC개의 줄을 출력한다. XX번째 테스트 케이스에서 작은 조각상을 큰 조각상에서 만들어 낼 수 있으면 Case #X: YES를, 만들어 낼 수 없으면 Case #X: NO를 출력한다. XX는 1부터 CC까지의 테스트 케이스 번호다.

힌트

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

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

예제3

  1. 예제 1

    입력
    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
    예상 출력
    Case #1: NO
Case #2: YES

  2. 예제 2

    입력
    1
2
1 2
1
    예상 출력
    Case #1: YES

  3. 예제 3

    입력
    5
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
3
1 2
2 3
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
7
1 2
1 3
1 4
1 5
1 6
1 7
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7
1 2
2 3
3 4
4 5
5 6
6 7
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 2
1 3
1 4
5
1 2
1 3
1 4
1 5
2
1 2
    예상 출력
    Case #1: YES
Case #2: YES
Case #3: YES
Case #4: NO
Case #5: YES