import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static int answer;
    private static boolean[][] map;

    public static int solution(int n, int[][] wires) {
        answer = -1;

        map = new boolean[n + 1][n + 1];

        // 송신탑 연결정보 세팅
        for (int i = 0; i < wires.length; i++) {
            int[] wire = wires[i];
            map[wire[0]][wire[1]] = true;
            map[wire[1]][wire[0]] = true;
        }

        // 네트워크 분리 시도
        for (int i = 0; i < wires.length; i++) {
            int[] wire = wires[i];

            Deque<Integer> stack = new ArrayDeque<>();
            stack.add(wire[0]);

            boolean[] topStatus = new boolean[map.length];
            topStatus[wire[0]] = true;

            int cnt = findInNetwork(wire, stack, topStatus, 1);

            int diff = Math.abs((n - cnt) - cnt);
            answer = answer < 0 ? diff : Math.min(diff, answer);
        }


        return answer;
    }

    private static int findInNetwork(int[] cutWire, Deque<Integer> stack, boolean[] topStatus, int cnt) {
        int currentTopNum = stack.pop();

        for (int i = 1; i < map.length; i++) {
            if (i != cutWire[1] && map[currentTopNum][i] && !topStatus[i]) {
                topStatus[i] = true;
                stack.add(i);
                cnt = findInNetwork(cutWire, stack, topStatus, cnt + 1);
            }
        }

        return cnt;
    }
}