eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Pink Floyd

Pink Floyd

Группа \textit{Pink Floyd} собирается отправится в новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист \textit{Роджер Уотерс} постоянно нервничает при перелётах. На некоторых маршрутах он теряет вес от волнения, а на других - много есть и набирает вес. Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелёты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она даёт концерты, при этом между концертами группа может посещать и промежуточные города. \InputFile Первая строка входного файла содержит три натуральных числа $n$, $m$ и $k$ - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно $(n ≤ 100, m ≤ 10000, 2 ≤ k ≤ 10000)$. Города пронумерованы числами от $1$ до $n$. Следующие $m$ строк содержат описание рейсов, по одному в строке. Рейс номер $i$ описывается тремя числами $b_i$, $e_i$ и $w_i$ - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах $(1 ≤ b_i, e_i ≤ n, -100000 ≤ w_i ≤ 100000)$. Последняя строка содержит числа $a_1, a_2, ..., a_k$ - номера городов, в которых проводятся концерты $(a_i ≠ a_{i+1})$. В начале концертного тура группа находится в городе $a_1$. Гарантируется, что группа может дать все концерты. \OutputFile Первая строка выходного файла должна содержать число $l$ - количество рейсов, которые должна сделать группа. Вторая строка должна содержать $l$ чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать сообщение `infinitely kind`.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные #1
6
5 6 5 7 2 3