6360: BZOJ2360：唯美村落

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

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

若a-->b且a-->c，则b、c之间一定无道路，且如果d-->b，那么，一定有d-->c.

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

输入格式

第一行包含两个正整数n，m。

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

接下来m行，每行三个正整数a,b,c，表示一条边，c=1代表a连向b，c=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；题给的都是“唯美村落”.

题目来源

没有写明来源