IOI 国所有铁路的拥有者、大富豪 JOI 先生已经去世。根据遗嘱，铁路将被分割并继承。
IOI 国有 个城市，以及连接这些城市的 条铁路。城市编号为 1 到 ，铁路编号为 1 到 。第 条铁路连接城市 和城市 ，为双向线路，每年可产生 日元的收益。由于乘客数量和票价各异， 各不相同。可能存在多条铁路连接同一对城市。
遗嘱中规定了铁路分割继承的方法如下：
- 铁路将由 JOI 先生的 个子女继承。子女按年龄从高到低依次编号为 1 到 。
- 每个子女继承若干条铁路（可能为 0 条）。
- 首先，从 条铁路中，子女 1 选择若干条作为自己的继承部分；接着，从剩余铁路中，子女 2 决定自己的继承部分；依此类推， 个子女依次决定继承部分。
- 任何子女都不能继承已被更年长子女继承的铁路。即，若铁路 已被子女 继承，则任何更年轻的子女 （）均不能继承该铁路。
- 任何子女在选择继承部分时，必须确保所选铁路不构成环路。即，若存在一条由铁路 （其中 互不相同）组成的路径，使得从某个城市出发，经过这些铁路后能返回原城市，则任何子女均不能独自继承所有这些铁路。
- 未被任何子女继承的铁路将捐赠给 IOI 国。
每个子女都像其父亲一样贪婪，希望自己的继承部分的年收益总和尽可能大。已证明，对于每个子女，存在唯一一种选择方式，使其继承部分的年收益总和达到最大值。请确定每条铁路由谁继承。
题目
给定 IOI 国铁路的信息和 JOI 先生子女的人数，编写程序求出每条铁路由谁继承。
