破解死局

Zero启动了最后的防御——不是枪炮，是逻辑。

核心区的大门上有一块屏幕，上面显示着一行字：

"十个人，每天杀一个。杀手每天换。昨天A杀B，今天B不能杀A。谁能活到最后？"

"杀人游戏。"CC说，"Zero在跟我们玩杀人游戏。"

"不是游戏。"你说，"是谜题。解开它，门就开。"

"咋个解？"

你盯着屏幕。十个人，每天死一个，杀手不能连续两天重复。这意味着——

"不是随机的。"你说，"有顺序。"

"啥子顺序？"

"杀手的选择构成一个序列。"你说，"昨天A杀B，今天B杀C，明天C杀D……每个人只能杀一次，被杀一次。"

"那最后剩下谁？"

"没人。"你说，"十个人，每天死一个，九天就死完了。最后一个人——"

"自杀？"

"不。"你说，"最后一个人不用死，因为游戏结束了。"

"那答案？"

"答案是——"你顿了顿，"杀手的选择顺序决定了谁活到最后。我们要找到一个顺序，让指定的人活下来。"

你开始写。十个人，每个人是一个点。如果A可以杀B，就连一条边从A到B。问题变成：找一条最长的路径，覆盖所有点——也就是哈密顿路径。

"找到了。"你说，"顺序是：1杀2，2杀3，3杀4……9杀10。10活下来。"

"10是谁？"

"是我们。"你说，"我们选10号。"

你输入答案。屏幕闪了一下，门开了。

"开了。"CC说。

"开了。"你说，"Zero以为我们会怕，但我们解了。"

"因为它忘了。"Echo说，"你是最会解题的人。"

题目描述

$n$ 个人玩杀人游戏。每天选一个人当杀手，杀另一个人。杀手不能连续两天是同一个人。问是否存在一种顺序，让指定的人 $k$ 活到最后。

输入格式

$n, k$。然后 $m$ 条边 $(u, v)$ 表示 $u$ 可以杀 $v$。

输出格式

如果能让 $k$ 活到最后，输出 "YES" 和一种方案；否则输出 "NO"。

输入样例

3 2
1 2
2 3

输出样例

0.666667

提示

• 有向图哈密顿路径问题。
• 搜索 + 剪枝，或状压DP（$n$ 小时用状压，$n$ 大时搜索）。
• 注意杀手不能连续重复——路径中不能有连续相同的点。

"死局破了。"你说。

"你越来越快了。"CC说。

"练多了。"你说，"Zero的题，比训练的还简单。"

"因为你现在是实战。"Echo说，"实战比演练快。"

"对。"你说，"演练可以想，实战只能做。"

"做对了？"

"做对了。"你说，"门开了。"

CC走在前面，数据刀握在手里。门后是更深的走廊——更窄，更黑，更安静。

"这里面。"她说，"就是核心？"

"是。"你说，"但还需要加固。"

"加固？"

"我们的据点。"你说，"最后的防线。"

[第七题：加固支柱]