#811. 排雷专家希蒙

排雷专家希蒙

题目描述

上一期说道希蒙在你的帮助下成功完成了战地通讯员的任务。现在希蒙又收到了新的任务---排雷。希蒙发现敌人逃跑后在n个区域(n≤200,区域以整数编号)埋了地雷,每个区域中埋有一定数量的地雷。同时,给出各区域之间的连接路径,并规定路径都是单向的,且保证都是小序号区域指向大序号区域,也不存在可以从一个区域出发经过若干区域后又回到原来区域的路径。希蒙可以从任意一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时排雷工作结束。请你帮助希蒙设计一个排雷方案,使他能排除最多的地雷。

输入输出格式

输入格式

第一行:地雷区域的个数;

第二行:为依次每个区域地雷的个数;

下面若干行:

xi yi表示从xi可到yi,xi<yi。

最后一行为"0 0"表示结束。

输出格式

两行

k1-k2…-kv //排雷的顺序

挖到最多的雷。

样例

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
3-4-5-6
34