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

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

정올이는 각 마을에서 시작하는 가장 긴 여행 일정을 알고 싶어한다. 시작하는 도시에 따라 여러 최장 여행 일정이 있을 수 있으며, 이 중에서도 도로 번호 순서가 사전적으로 최소인 여행 일정을 선호한다. 두 여행 목록의 길이가 같을 때 첫 번째 여행 일정이 두 번째 여행 일정보다 작은 요소를 가지고 있으면 첫 번째 여행 일정은 두 번째 여행 일정보다 사전적으로 작다.

각 마을에서 시작하는 것이 가능한 여행 일정 중 정올이가 가장 선호하는 여행 일정의 길이와 도로 레이블 합계를 출력하세요.

#6097 upload 21 done 6 how_to_reg 4 call_split Subtask

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

#6097
Subtask

최장 여행 일정 2s 1024MB