Андрей предпочитает такси другим видам транспорта, но вот в последнее время таксисты начали вести себя неподобающим образом. Для того, чтобы стрясти побольше денег с пассажира, они порой не против прокатиться по кругу, иногда даже не единожды. Дороги в городе Андрея односторонние, и, вообще говоря, не всегда из одной части города можно добраться до другой. Но к особенностям дорог все привыкли, а вот к ушлым таксистам нет.
Мэр города решил поменять направления некоторых дорог таким образом, чтобы таксист больше не смог бесконечно увеличивать счетчик клиента. Другими словами, таксист, находящийся на конкретном перекрестке, не мог бы попасть на него повторно, совершив ненулевой маршрут.
Для того, чтобы поменять направление дороги, нужны регулировщики. Для каждой конкретной дороги известно, сколько регулировщиков нужно, чтобы поменять направление дороги на противоположное. Разрешено менять направление дорог последовательно, то есть одни и те же регулировщики могут поучаствовать в изменении нескольких дорог.
Необходимо вычислить минимальное количество регулировщиков, необходимых для выполнения задания, и список дорог, у которых необходимо поменять направление.
Выходные данные
В первой строке выведите два целых числа — минимальное число регулировщиков, необходимых для выполнения задания и количество дорог \(k\), у которых необходимо поменять направление. \(k\) не должно быть минимальным.
В следующей строке через пробел выведите \(k\) целых чисел — номера дорог, у которых необходимо поменять направление. Дороги нумеруются с \(1\) в порядке следования во входных данных. Если существует несколько решений, выведите любое из них.
Примечание
В первом примере имеется два простых цикла: \(1 \rightarrow 5 \rightarrow 2 \rightarrow 1\) и \(2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2\). Один регулировщик сможет развернуть только дорогу \(2 \rightarrow 1\), второй цикл в одиночку он разрушить не сможет. Два регулировщика уже смогут развернуть дороги \(2 \rightarrow 1\) и \(2 \rightarrow 3\), после чего не останется перекрестка, на который можно попасть снова, совершив ненулевой маршрут.
Во втором примере одного регулировщика недостаточно, чтобы разрушить маршрут \( 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \). С помощью трёх регулировщиков можно, например, развернуть дороги \(1 \rightarrow 3\) ,\( 2 \rightarrow 4\), \(1 \rightarrow 5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
|
2 2
1 3
|
|
2
|
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3
|
3 3
3 4 7
|