1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import deque
def BFS(graph,root,dis):
    visit = set()
    queue = deque([root])
    visit.add(root)

    while queue:
        n = queue.popleft()
        if n not in graph:
            break
        for i in graph[n]:
            if i not in visit:
                visit.add(i)
                queue.append(i)
                dis[i] = dis[n] +1
    return dis
def solution(n, edge):
    answer = 0

    a = sorted([sorted(i) for i in edge])
    b = sorted([sorted(i,reverse = True) for i in edge])
    c = a+b

    dicver = {}
    for i in c:
        if i[0] in dicver:
            dicver[i[0]].append(i[1])
        else:
            dicver[i[0]] = [i[1]]
    distance = dict.fromkeys(dicver.keys(),0)

    result = BFS(dicver,1,distance)
    answer = len([k for k,v in result.items() if max(result.values()) == v])
    return answer