현대 미술 표절

두 조각품의 사진이 있다. 조각품은 여러 개의 속이 꽉 찬 금속 구와 구의 쌍을 연결하는 몇 개의 고무관으로 이루어져 있다. 각 조각품의 관은 임의의 구 쌍에 대해, 그 두 구 사이에 일련의 관을 따라가는 경로가 정확히 하나만 존재하도록 연결되어 있다(어떤 관도 반복해서 지나지 않는다). 모든 구의 반지름은 같고, 모든 관의 길이도 같다.

두 조각품 중 작은 조각품이 사실 큰 조각품에서 구와 관을 일부 제거하기만 해서 만들어졌다고 의심하고 있다. 이것이 가능한지 검사하는 프로그램을 작성하려고 한다.

입력에는 여러 테스트 케이스가 포함된다. 각 조각품은 구에 1부터 연속으로 번호를 매기고, 관으로 연결된 구의 쌍을 나열하여 설명한다. 번호는 각 조각품마다 독립적으로 정한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ C ≤ 100 2 ≤ N ≤ 8 1 ≤ M < N

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ C ≤ 50 2 ≤ N ≤ 100 1 ≤ M < N

• 입력 파일의 테스트 케이스 수인 정수 C가 한 줄에 주어진다.

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

• 큰 조각품에 있는 구의 수인 정수 N이 한 줄에 주어진다.

• N−1개의 줄이 주어지며, 각 줄에는 공백으로 구분된 정수 한 쌍이 주어진다. 이는 큰 조각품에서 해당 번호를 가진 두 구가 관으로 연결되어 있음을 나타낸다.

• 작은 조각품에 있는 구의 수인 정수 M이 한 줄에 주어진다.

• M−1개의 줄이 주어지며, 각 줄에는 공백으로 구분된 정수 한 쌍이 주어진다. 이는 작은 조각품에서 해당 번호를 가진 두 구가 관으로 연결되어 있음을 나타낸다.

• 입력 파일에 등장하는 순서대로 각 테스트 케이스마다 한 줄씩, 총 C개의 줄을 출력한다. 케이스 X의 작은 조각품을 케이스 X의 큰 조각품으로부터 만들 수 있었다면 "Case #X: YES"을, 만들 수 없었다면 "Case #X: NO"을 출력한다. (X는 1부터 C 사이인 테스트 케이스의 번호이다.)

첫 번째 케이스에서 큰 조각품은 구 다섯 개가 일렬로 연결되어 있고, 작은 조각품은 구 하나에 다른 구 세 개가 연결되어 있다. 큰 조각품에서 일부를 제거하여 작은 조각품을 만드는 방법은 없다.

두 번째 케이스에서 작은 조각품은 구 네 개가 일렬로 연결되어 있다. 이들은 큰 조각품의 구와 2-1-4-5 순서로 대응시킬 수 있다.