Problem
Perusahaan "Auto-2010" menghasilkan enjin untuk kereta yang terkenal di dunia. Enjin ini mengandungi tepat n bahagian, bernombor dari 1 hingga n, manakala bahagian dengan nombor i dibuat dalam pi saat. Spesifik perusahaan "Auto-2010" ialah hanya satu bahagian enjin boleh dihasilkan di sana pada satu masa. Sesetengah bahagian memerlukan set pasang siap bahagian lain untuk dihasilkan.
Ketua Pengarah "Auto-2010" tetapkan tugas yang bercita-cita tinggi untuk perusahaan — untuk menghasilkan bahagian nombor 1 dalam masa yang paling singkat untuk membentangkannya di pameran.
Ia dikehendaki menulis program yang, memandangkan kebergantungan susunan pengeluaran antara bahagian, akan mencari masa paling singkat di mana ia mungkin untuk menghasilkan nombor bahagian 1.
Input
Baris pertama fail input mengandungi nombor n (1≤ n ≤ 100000) — bilangan bahagian enjin. Baris kedua mengandungi n integer positif p
1, p
2, p
n, yang mentakrifkan masa pembuatan setiap bahagian dalam saat. Masa untuk membuat setiap bahagian tidak melebihi 10
9 saat.
Setiap baris n seterusnya bagi fail input menerangkan ciri-ciri pengeluaran bahagian. Di sini baris ke-i mengandungi bilangan bahagian ki yang diperlukan untuk menghasilkan nombor bahagian i, serta nombornya. Tiada nombor bahagian pendua dalam baris ke-i. Jumlah semua nombor k
i tidak melebihi 200000.
Adalah diketahui bahawa tiada kebergantungan kitaran dalam pengeluaran bahagian.
Cetakan
Baris pertama fail output harus mengandungi dua nombor: masa minimum (dalam saat) yang diperlukan untuk menghasilkan nombor bahagian 1 secepat mungkin dan bilangan k bahagian yang perlu dihasilkan untuk ini. Dalam baris kedua anda perlu mencetak k nombor yang dipisahkan ruang — nombor bahagian mengikut susunan yang sepatutnya dihasilkan untuk menghasilkan nombor bahagian 1 secepat mungkin.
| Input |
Output |
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
|