만드는 중입니다

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

도시 관광 (작은 입력)

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

요약
한 번에 하나의 삼각형씩 성장한 도시에서 각 거리와 지점을 최대 한 번씩만 써서 닫힌 관광 경로가 방문할 수 있는 가장 많은 지점 수를 구합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 그래프
정답자
아직 제출이 없습니다

문제

여름이면 유럽의 오래된 도시는 거리를 걸으며 명소를 찾는 관광객으로 붐빈다.

이런 도시 상당수는 설계도 없이 자라났지만 자라난 방식은 서로 비슷하다. 도시는 명소 세 곳에서 시작했고, 세 곳은 두 곳씩 서로 양방향 도로로 이어져 있었다. 그 뒤로 명소가 하나씩 늘어났다. 새 명소는 이미 도로로 직접 이어져 있던 서로 다른 두 명소와 각각 새 양방향 도로로 연결되었다.

관광객은 되도록 많은 명소를 도는 관광 코스를 짜려고 한다. 코스는 아무 명소에서나 출발할 수 있고, 출발한 명소로 반드시 돌아와야 한다. 같은 도로는 최대 한 번만 지날 수 있고, 같은 명소도 최대 한 번만 방문할 수 있다. 출발한 명소만 정확히 두 번 방문한다.

도시가 자라난 과정이 주어진다. 코스 하나가 방문할 수 있는 서로 다른 명소의 최대 개수를 구하라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 명소 개수 NN이 주어진다. 명소에는 1번부터 NN번까지 번호가 붙어 있다. 1번, 2번, 3번은 도시가 시작할 때의 세 명소이고, 4번부터 NN번까지는 도시에 추가된 순서대로 번호가 붙어 있다.

다음 N−3N-3개의 줄에는 공백으로 구분된 두 정수 AA와 BB가 주어진다. 해당 명소가 AA번 명소, BB번 명소와 도로로 연결되었다는 뜻이다. 첫 줄은 4번 명소, 둘째 줄은 5번 명소, 그다음 줄은 6번 명소에 해당하는 식이다.

제한

  • 1≤T≤501 \le T \le 50
  • 4≤N≤154 \le N \le 15
  • A≠BA \ne B이고, 새 명소가 추가되는 시점에 AA번 명소와 BB번 명소는 이미 도로로 직접 이어져 있다.

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 관광 코스 하나가 방문할 수 있는 명소의 최대 개수이다.

예제4

  1. 예제 1

    입력
    2
5
1 2
2 1
6
1 2
1 4
4 5
    예상 출력
    Case #1: 4
Case #2: 6

  2. 예제 2

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

  3. 예제 3

    입력
    1
15
1 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
    예상 출력
    Case #1: 15

  4. 예제 4

    입력
    12
4
1 2
5
1 3
1 3
6
1 3
1 2
1 2
7
1 2
1 3
1 4
2 3
8
1 3
1 2
1 4
4 6
3 4
9
2 3
2 4
1 3
3 4
1 6
4 7
10
1 2
1 3
1 5
1 6
1 6
1 3
1 5
11
2 3
1 3
2 3
2 4
2 4
2 3
3 4
3 10
12
1 3
1 3
3 5
1 2
3 6
1 2
5 6
2 7
3 5
13
1 2
2 4
2 3
1 3
4 5
2 6
2 9
6 9
6 9
6 9
14
2 3
3 4
4 5
1 2
3 5
4 5
1 2
1 10
1 7
1 11
1 3
15
1 3
1 3
3 4
2 3
1 2
3 4
4 6
3 7
2 7
1 5
1 8
1 5
    예상 출력
    Case #1: 4
Case #2: 4
Case #3: 5
Case #4: 7
Case #5: 8
Case #6: 9
Case #7: 7
Case #8: 8
Case #9: 9
Case #10: 11
Case #11: 11
Case #12: 11