import java.util.*;

class Solution {
      public static int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < edge.length; i++) {
            int[] line = edge[i];
            int node1 = line[0];
            int node2 = line[1];

            map.computeIfAbsent(node1, k -> new ArrayList<>()).add(node2);
            map.computeIfAbsent(node2, k -> new ArrayList<>()).add(node1);
        }

        return calcDistance(map, n);
    }

    private static int calcDistance(Map<Integer, List<Integer>> map, int n) {
        int longestNum = 0;
        int longestCnt = 0;
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;

        int[] lineNumArr = new int[n + 1];
        Queue<Integer> queue = new ArrayDeque<>();

        // 1번과 연결된 노드 리스트
        List<Integer> nodeList = map.get(1);
        for (int node : nodeList) {
            if (!visited[node]) {
                queue.add(node);
                lineNumArr[node] = lineNumArr[node] + 1;
                visited[node] = true;
                longestNum = 1;
                longestCnt++;
            }
        }

        // 1번과 연결되지 않은 노드 중 가장 짧은 거리 탐색
        while (!queue.isEmpty()) {
            int node = queue.poll();
            List<Integer> nextNodeList = map.get(node);

            if (nextNodeList == null) continue;

            for (int nextNode : nextNodeList) {
                if (!visited[nextNode]) {
                    queue.add(nextNode);
                    lineNumArr[nextNode] = lineNumArr[node] + 1;
                    visited[nextNode] = true;

                    if (longestNum < lineNumArr[nextNode]) {
                        longestNum = lineNumArr[nextNode];
                        longestCnt = 1;
                    } else if (longestNum == lineNumArr[nextNode]) {
                        longestCnt++;
                    }
                }
            }
        }

        return longestCnt;
    }
}