Безумный ученый Майк устроился на работу. Его задача — управлять системой насосных станций для перекачки воды.

Система состоит из n насосных станций, которые пронумерованы целыми числами от 1 до n. Некоторые пары станций соединены двунаправленными трубами, по которым может течь вода в том или другом направлении (но одновременно только в одном). Для каждой трубы задана пропускная способность — наибольшее количество литров воды, которое может через нее протекать в течение одного часа. Каждая насосная станция может перекачивать входящую воду из одних станций в другие станции по трубам при условии, что за один час общее входящее в эту станцию количество литров воды равняется общему исходящему из этой станции количеству литров воды.

В обязанности Майка входит перекачивание воды между станциями. Из станции a в станцию b по трубам (возможно, через другие станции) в течение одного часа можно пустить какое-то количество литров воды согласно правилам, описанным выше. В течение этого времени вода из других станций не может втекать в станцию a, и не может вытекать из станции b, при том из станции a может вытекать любое количество воды, и в станцию b может втекать любое количество воды. Если из станции a за час в общем было выкачано x литров воды, то Майк получает к зарплате x бублей.

Чтобы получить зарплату, Майк по контракту должен работать n - 1 дней. В первый день он выбирает две станции v₁ и v₂, и в течение одного часа перекачивает определённое количество воды из v₁ в v₂. Далее в i-тый день Майк выбирает до этого ни разу не выбранную станцию v_i + 1, и в течение одного часа перекачивает определенное количество воды из станции v_i в станцию v_i + 1. При этом количество перекачиваемой воды в i-тый день не зависит от количества перекачиваемой воды в (i - 1)-ый день.

Для своих проектов Майку нужно заработать как можно больше бублей. Помогите Майку найти такую перестановку номеров станций v₁, v₂, ..., v_n, при которой Майк может заработать наибольшую возможную зарплату.