【UNR #4】挑战哈密顿
这是一道提交答案题。比赛时提交此题显示的成绩就是最终成绩。
在线性解决三染色后，出题人 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$ 个正整数，表示路径依次经过的点的序列。
3 3
3 3 3 3 3 3 3 3 3 3
1 2
1 3
2 3
3
1 2 3
注意边是有向的。
选手的提交在该测试点上可以获得 10 分。
4 4
1 1 2 2 3 3 4 4 4 4
1 2
2 1
1 3
4 2
2
2 1
选手的提交在该测试点上可以获得 4 分。
注意你不需要提交最优解。
评分标准
对于每个测试点:
- 若你的输出不合法，你的得分为0。否则设你的方案中节点个数个数为$k$。
- 你的得分为 $\sum \limits_{i=1}^{10} [k \ge a_i]$，即你的 $k$ 大于等于多少个 $a_i$ ，就得几分。
数据范围
对于所有数据，满足$1 \le n,m \le 500000$。
保证无重边、自环，且存在至少一条哈密顿路径。