차원의 나무 여행

• 풀이는 공식 풀이 참고. 증명만 떠올리면 코드는 간단하다.
• 주어진 트리가 star graph인 경우만 제외하면, 모든 이동을 워프로 할수 있으므로 N을 출력. star graph라면 한번은 워프를 못하고 간선을 따라 이동해야 하므로, N-1을 출력.

"""Solution code for "BOJ 32755. 차원의 나무 여행".

- Problem link: https://www.acmicpc.net/problem/32755
- Solution link: http://www.teferi.net/ps/problems/boj/32755

Tags: [tree]
"""

from teflib import tree as ttree


def main():
    N, tree = ttree.create_tree_from_input()
    is_star_graph = max(len(neighbors) for neighbors in tree) == N - 1
    print(N - 1 if is_star_graph else N)


if __name__ == '__main__':
    main()