#P2360. 唯美村落

    ID: 1403 传统题 1000ms 128MiB 尝试: 18 已通过: 9 难度: 8 上传者: 标签>CF2500提高+/省选-二分图建模普通并查集缩点欧拉回路Hierholzer 算法

唯美村落

题目描述

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

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

若 a→ba\rightarrow b 且 a→ca\rightarrow c,则 b,cb,c 之间一定无道路,且如果 d→bd\rightarrow b,那么,一定有 d→cd\rightarrow c。

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

输入格式

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

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

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

输出格式

如果原图不存在 Hamilton 回路,则输出 -1;否则输出 nn 行,为 1∼n1\sim 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%30\% 的数据满足 n≤100n\le 100,m≤103m\le 10^3

100%100\% 的数据满足 3≤n≤2×1043\le n\le 2\times 10^4,m≤5×105m\le 5\times 10^5;题给的都是「唯美村落」。