def solution(n, edge):
    '''
    input: 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex
    output: 1번 노드로부터 가장 멀리 떨어진 노드(최단경로로 이동했을 때 간선의 개수가 가장 많은 노드)가 몇 개인지
    각 노드는 1부터 n까지 번호가 적혀있음
    '''
    answer = 0
    # 각 node가 어떤 node와 연결되어 있는지 정리
    tree = [[] for i in range(n)]
    for i in range(1,n+1):
        for e in edge:
            e.sort()
            if i in e: tree[i-1].append(e)
    max_count = 0
    for t in tree[0]: # 1번째 node에 대해,
        temp_count = 1
        dest_node = t[1]
        steps = [1]
        while True:
            new = tree[dest_node-1]
            steps.append(dest_node)
            temp_count += 1
            # 종료조건 1: 모든 탐색이 끝난 경우
            if len(steps) == n: break
            # 종료조건 2: 마지막 node인 경우
            if len(new)==1: break
            # 다음 node로 넘어가기
            for i in range(2, n+1):
                if i not in steps:
                    dest_node = i
        max_count = max(max_count, temp_count)

    answer = max_count
    return answer

import queue
# with BFS
def solution(n, edge):
    '''
    input: 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex
    output: 1번 노드로부터 가장 멀리 떨어진 노드(최단경로로 이동했을 때 간선의 개수가 가장 많은 노드)가 몇 개인지
    각 노드는 1부터 n까지 번호가 적혀있음
    '''
    answer = 0
    # 각 node가 어떤 node와 연결되어 있는지 정리
    nodeList = []
    adjencyList = [[] for i in range(n+1)]
    for e in edge: #각각 1~n이 어떤 vertex와 edge를 가지고 있는지
        adjencyList[e[0]].append(e[1])
    #print(adjencyList)
    q=queue.Queue()
    q.put(1)
    visitedVertex = []
    while q.qsize():
        current = q.get()
        for neighbor in adjencyList[current]: # 해당 node에 연결되어 있는 애들 파악하기
            if not neighbor in visitedVertex:
                visitedVertex.append(neighbor)
                if len(adjencyList[neighbor])==1: break
                else:
                    for nei in adjencyList[neighbor]:
                        q.put(nei)
            #
            #    q.put(neighbor)
        #visitedVertex.append(current)

    answer = len(visitedVertex)
    return answer