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