Стабилизация мультивселенной
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аномалии очень опасны тем, что могут изменять естественный ход событий, и даже вмешиваться в ключевые события, что может повлечь за собой необратимые последствия для многих вселенных. После того, как Пятно появился на Земле-2099, он нарушил столько ключевых событий, что аж $$$n$$$ соседних вселенных под угрозой: паутина мультивселенной расплетается. И вам предстоит это исправить!

Для того, чтобы стабилизировать вселенные, в которых открылись квантовые дыры, необходимо заново связать их вместе, пустив между ними потоки космической энергии. Известно, что:

  1. некоторые пары вселенных связаны односторонними энергетическими каналами;
  2. из каждой из $$$n$$$ вселенных выходят ровно два канала;
  3. в каждую из $$$n$$$ вселенных ведут ровно два канала;
  4. каждый канал характеризуется парой чисел $$$a$$$ и $$$b$$$, которые означают, что мощность энергии, пущенной по этому каналу, должна лежать между $$$a$$$ и $$$b$$$ включительно.

Вам необходимо выбрать ровно $$$n$$$ каналов так, чтобы они образовывали циркуляцию энергии, затрагивающую каждую из $$$n$$$ вселенных. Иными словами, эти $$$n$$$ каналов должны образовывать несколько (один или более) циклов, проходящих в совокупности по всем $$$n$$$ вселенным.

При этом мощность энергии, пускаемой по каждому выбранному каналу, должна быть одинакова (даже если каналы находятся на разных циклах). Более формально, должно существовать такое значение мощности $$$w$$$, что на каждом выбранном канале $$$a_i \le w \le b_i$$$.

Определите, можно ли выбрать такие каналы, и такое значение мощности, чтобы все требуемые условия были выполнены. Спасите мультивселенную!

Входные данные

В первой строке ввода дано единственное целое число $$$n$$$ — количество рассматриваемых вселенных ($$$3 \le n \le 10^5$$$).

В следующих $$$2n$$$ строках перечислены энергетические каналы: сначала даны два канала, исходящих из вселенной номер $$$1$$$, затем два канала, исходящих из вселенной номер $$$2$$$, и так далее. Описание каждого канала задается тремя целыми числами $$$t_i$$$, $$$a_i$$$ и $$$b_i$$$ — номером вселенной, в которую он ведет, и ограничениями на мощность пускаемой по нему энергии ($$$1 \le t_i \le n$$$; $$$1 \le a_i \le b_i \le 10^5$$$).

Гарантируется, что в каждую вселенную ведет ровно два канала. Никакой канал не соединяет вселенную с самой собой, но может быть два канала между одними и теми же вселенными.

Выходные данные

В первой строке выведите единственное число -1, если способа выбрать циркуляцию одной мощности не существует.

Иначе — выведите в первой строке искомое значение мощности энергии $$$w$$$. После чего во второй строке выведите ровно $$$n$$$ целых чисел через пробел — номера выбранных каналов (от $$$1$$$ до $$$2n$$$) в порядке их следования во вводе.

Если подходящих ответов несколько, выведите любой из них.

Примеры

Входные данные
3
2 1 3
3 4 5
3 2 4
1 1 5
1 3 5
2 6 7
Выходные данные
3
1 3 5 
Входные данные
5
2 3 6
3 4 6
5 4 8
5 7 8
4 1 6
1 2 4
2 2 9
3 5 7
4 1 3
1 5 8
Выходные данные
6
1 3 5 8 10

Примечание

В первом примере выбираются каналы под номерам $$$1$$$, $$$3$$$ и $$$5$$$. Первый ведет из вселенной номер $$$1$$$ во вселенную номер $$$2$$$ и имеет ограничения на энергию $$$[1, 3]$$$. Аналогично, третий идет из вселенной $$$2$$$ во вселенную $$$3$$$ с ограничениями $$$[2, 4]$$$, и пятый ведет из вселенной $$$3$$$ во вселенную $$$1$$$ с ограничениями $$$[3, 5]$$$. Получаем цикл $$$1 \to 2 \to 3 \to 1$$$, проходящий по всем вселенным, по каждому каналу которого можно пустить энергию с мощностью $$$3$$$.

Во втором примере получается два цикла $$$1 \to 2 \to 5 \to 1$$$ и $$$3 \to 4 \to 3$$$. По каждому из выбранных каналов можно пустить энергию мощности $$$6$$$.