민우는 오늘 있었던 프로그래밍 과목 중간고사를 망쳐서 기분이 좋지 않다. 민우는 스트레스도 풀 겸 시험 문제로 나온 그래프를 불로 태우려고 한다.

민우는 그래프의 정점 (위 그림에서 동그라미로 표시된 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 곧바로 노드와 연결된 간선을 따라서 불이 전달된다. 간선 위에서는 불은 1초당 1만큼의 거리를 이동한다. 만약 어떤 간선의 양 끝 정점에 불이 붙은 경우 불은 간선의 중앙까지 태운 후 꺼진다.

민우는 그래프를 최대한 빠른 시간 안에 전부 태우고 싶어한다. 민우를 도와 어떤 정점에 불을 붙일지 구하는 프로그램을 작성하여라. 단, 위 그림에서 간선끼리 교차하는 것은 무시하여라.

#3018 upload 36 done 13 how_to_reg 12

그래프 태우기 timer 1s memory 128MB

#3018

그래프 태우기 1s 128MB