这是一道提交答案题。比赛时提交此题显示的成绩就是最终成绩。

在线性解决三染色后，出题人 03 着手于研究图上哈密顿链问题：给你一个 $n$ 个点，$m$ 条边的有向图，请你找到一条经过每个结点恰好一次的路径。

03 生成了一大堆图，在确定这些图都存在至少一条哈密顿链之后，03 便扔给了选手。

看到选手面露难色，03 摆了摆手：“不要那么为难自己。如果找不到哈密顿链，那么告诉我一条尽量长的且不重复经过结点的路径就好了。”

选手立刻拍了桌子：“即使是求最长路，也是 NP 完全问题啊！出题人怎么能随便找个 NP 完全问题随便找几个图，就把题出出来了呢？”

但 03 背过身去指了指考场上高高挂起的横幅 “沉着冷静，认真答题” 就走了。

选手冷静下来之后果然发现数据有蹊跷。虽然测试点各有特点，但存在一个统一的简洁算法能够通过所有测试点。那么聪明的你也能发现这个算法吗？

输入格式

这是一道提交答案题，共有 $10$ 组输入数据，这些数据命名为 hamil1.in ~ hamil10.in。

第一行两个正整数 $n,m$。

第二行 $10$ 个数字，第 $i$ 个数字表示 $a_i$,表示评分参数。

接下来 $m$ 行，每行 $2$ 个正整数 $u,v$，表示有一条从 $u$ 到 $v$ 的有向边。

输出格式

对于每组输入数据，你需要提交相应的输出文件 hamil1.out ~ hamil10.out。

每组数据第一行一个正整数 $k$，表示路径上节点个数。

第二行 $k$ 个正整数，表示路径依次经过的点的序列。

样例一

input

3 3
3 3 3 3 3 3 3 3 3 3
1 2
1 3
2 3

output

3
1 2 3

explanation

注意边是有向的。

选手的提交在该测试点上可以获得 10 分。

样例二

input

4 4
1 1 2 2 3 3 4 4 4 4
1 2
2 1
1 3
4 2

output

2
2 1

explanation

选手的提交在该测试点上可以获得 4 分。

注意你不需要提交最优解。

评分标准

对于每个测试点:

• 若你的输出不合法，你的得分为0。否则设你的方案中节点个数个数为$k$。
• 你的得分为 $\sum _{i=1}^{10}[k\ge a_i]$，即你的 $k$ 大于等于多少个 $a_i$ ，就得几分。

数据范围

对于所有数据，满足$1\le n,m\le 500000$。

保证无重边、自环，且存在至少一条哈密顿路径。

下载

输入数据及checker下载