"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/86971
"""

# 풀이 과정
# 네트워크 2개로 분활 (나누어진 송전탑 개수 거의 비슷하게!)
# 목표 나누어진 송전탑들의 차이를  return

from collections import deque


def bfs(graph, d):
    visited = []
    queue = deque([d])

    while queue:
        n = queue.popleft()

        if n not in visited:
            visited.append(n)
            queue += graph[n]

    return visited


def solution(n, wires):
    # 탑의 개수
    top = [(a + 1) for a in range(n)]
    result = n - 2  # 송전탑 개수 차이 최대(한 쪽 n-1, 한 쪽 1)

    for b in range(len(wires)):
        k = wires.copy()
        k.pop(b)  # 간선을 하나씩 제거
        graph = {}

        for c, d in k:
            if c not in graph:
                graph[c] = [d]
            else:
                graph[c] += [d]

            if d not in graph:
                graph[d] = [c]
            else:
                graph[d] += [c]

        check = bfs(graph, d)

        num = abs(n - len(check) - len(check))

        if num < result:
            result = num

    return result