정올랜드에는 1부터 N까지 번호가 매겨진 N개의 마을과 M개의 단방향 도로이 있다. i번째 도로는 마을 a_i에서 출발하여 b_i로 도착하며, 라벨 l_i가 붙어 있다.

길이 k의 여행 일정이란 x_0번 마을에서 시작하는 x_0,x_1,…,x_k의 수열로 이루어진다. 이때, 모든 0 \le i \le k에 대하여 x_i번 마을에서 x_{i+1}번 마을로 이동하는 길이 존재하며, 무한한 길이의 여행 일정이 없음이 보장되고, 동일한 마을 쌍을 연결하는 도로는 둘 이상 존재하지 않는다.

정올이는 각 마을에서 시작할 수 있는 가장 긴 여행 일정을 알고 싶어한다. 어떤 마을에서는 최장 여행 일정이 여러 개 존재할 수 있는데, 이 중 도로 라벨 수열이 사전순으로 가장 작은 여행 일정을 선호한다.

같은 길이의 두 수열이 있을 때, 처음으로 서로 다른 위치에서 더 작은 라벨 값을 가진 수열이 사전순으로 더 작다.

각 마을마다 정올이가 선택한 여행 일정의 길이와, 그 여행에서 지나간 도로 라벨들의 합을 출력하라.

#6097 upload 19 done 6 how_to_reg 5 call_split Subtask

최장 여행 일정 timer 2s memory 1024MB

#6097
Subtask

최장 여행 일정 2s 1024MB