Problem
엔터프라이즈 "Auto-2010" 세계적으로 유명한 자동차용 엔진을 생산합니다. 엔진은 1에서 n까지의 번호가 매겨진 정확히 n개의 부품으로 구성되며, 숫자 i의 부품은 파이초 단위로 만들어집니다. 기업 "Auto-2010"의 특성 한 번에 하나의 엔진 부품만 제조할 수 있다는 것입니다. 일부 부품은 조립식으로 제작된 다른 부품 세트가 필요합니다.
"Auto-2010" 총감독 기업을 위한 야심 찬 작업 설정 — 가장 짧은 시간에 1번 부품을 생산하여 전시회에 선보입니다.
부품 간의 생산 순서 종속성이 주어지면 부품 번호 1을 생산할 수 있는 최단 시간을 찾는 프로그램을 작성해야 합니다.
입력
입력 파일의 첫 번째 줄에는 숫자 n(1≤ n
1, p2, pn이 포함됩니다. 각 부품을 만드는 시간은 109초를 초과하지 않습니다.
입력 파일의 다음 n행 각각은 부품 생산의 특성을 설명합니다. 여기서 i번째 줄에는 부품 번호 i를 생산하는 데 필요한 부품 ki의 수와 해당 번호가 포함됩니다. i번째 줄에는 중복된 부품 번호가 없습니다. 모든 숫자 ki의 합계는 200000을 초과하지 않습니다.
부품 생산에는 순환 종속성이 없는 것으로 알려져 있습니다.
출판물
출력 파일의 첫 번째 줄에는 부품 번호 1을 가능한 한 빨리 생산하는 데 필요한 최소 시간(초)과 이를 위해 생산해야 하는 부품 수 k의 두 가지 숫자가 포함되어야 합니다. 두 번째 줄에는 공백으로 구분된 k개의 숫자를 인쇄해야 합니다 — 부품 번호 1을 최대한 빨리 생산하기 위해 생산해야 하는 순서대로 부품 번호를 지정합니다.
<몸>
| 입력 |
출력 |
3
100 200 300
1 2
0
2 2 1
| 300 2
2 1
|
2
23
1 2
0 |
5 2
2 1
|
4
2 3 4 5
2 3 2
1 3
0
2 1 3
| 9 3
3 2 1
|