# 구현 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import sys # 그래프 # 1 ----- 2 ----- 6 # \ / \ / # \ / 4 - 5 # \ / / \ # 3 - 7 - 8 - 9 # 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9 # 9 12 (노드갯수, 간선정보) # 1 2 # 1 3 # 2 3 # 2 4 # 2 6 # 3 7 # 4 5 # 4 7 # 4 8 # 5 6 #..