唯美村落

时间限制:10s      空间限制:128MB

题目描述

很久以前,有一个美丽的村落,村落由n间房屋和m条道路构成,每个房子连出的边都不会指向它自身。道路可能是单向的,也可能是双向的,两个房子之间不会有多条道路。如果从房屋a仅走一条道路可以到达房屋b,则称a-->b.

这个村落的道路遵循着如下“唯美”的规律:

a-->ba-->c,则bc之间一定无道路,且如果d-->b,那么,一定有d-->c.

由此,这个村落就有了“唯美村落”之称,某一天,小P想从某个房屋出发,沿着道路拜访每个房屋恰一次,最后回到开始的房屋。小P知道这是经典的Hamilton回路问题,一般人在多项式时间内是解决不了的,但他相信你能解决。另外,小鹏提出了更高的要求,他给每个房屋定了一个重要值,各房屋的重要程度互不相同,他将把起点选在最重要的房屋上,然后尽量先访问重要值大的房屋,即要求依次访问的房屋的重要值组成的序列的字典序尽量大。


输入格式

第一行包含两个正整数nm

第二行包含n个用空格隔开整数,分别表示每个房屋的重要值。

接下来m行,每行三个正整数a,b,c,表示一条边,c=1代表a连向bc=2代表这是一条双向边。


输出格式

如果原图不存在Hamilton回路,则输出-1;否则输出n行,为1~n的一个排列,即最佳的Hamilton回路,排列的第一个数为起点,最后一个数实际上是连向起点的。


样例输入

5 7

50 40 30 20 10

1 3 2

1 4 2

2 3 1

2 4 1

3 5 1

4 5 1

5 2 1


样例输出

1

3

5

2

4


提示

【数据规模】

30%的数据满足,n<=100,m<=1000;

100%的数据满足,3<=n<=20000,m<=500000;题给的都是“唯美村落”.


题目来源

没有写明来源

Menuappsclose