#2360. 唯美村落

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

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

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

由此，这个村落就有了“唯美村落”之称，某一天，小P想从某个房屋出发，沿着道路拜访每个房屋恰一次，最后回到开始的房屋。小P知道这是经典的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