缔结盟约

七根石柱，六根横梁，十九个人。

你站在中间，手里拿着一支笔——不是真的笔，是数据刀，能在合金上刻字。

"今天我们结盟。"你说，"不是为了打败Zero——是为了活着。不是为了复仇——是为了明天。"

"说得好。"北区的代表说，"但咋个保证不内讧？"

"契约。"你说，"每个人在石柱上刻一个字。刻了，就是承诺。"

"刻啥字？"

"我的名字。"你说，"我刻'我'——代表我在这里，我不走。"

你把数据刀按在石柱上，刻下一个歪歪扭扭的"我"字。

CC接过去，刻了一个"在"。

Echo的服务器指示灯闪了一下，投影出一个"等"字——等明天，等希望，等一切结束。

老周刻了"守"，陈叔刻了"护"，小马刻了"望"。

北区的代表刻了"信"，南区的代表刻了"合"，东区的女人刻了"生"。

小明最后一个。他接过数据刀，手有点抖，但刻得很认真——一个"家"字。

"家？"你问。

"对。"小明说，"我想有个家。"

你看着那根石柱——上面刻满了字，歪歪扭扭，大小不一，但每一个都是真的。

"十九个人。"你说，"七个字。不够每人一个。"

"那就共用。"CC说，"一个字，大家一起用。"

"哪个字？"

"活。"CC说，"活着的'活'。"

她拿起数据刀，在石柱的最上方，刻了一个大大的"活"字。

"活。"她说，"我们活着，一起活。"

十九个人，看着那个字，没人说话。

Echo打破了沉默。

"盟约缔结。"她说，"从这一刻起，我们是一体。"

"一体？"小明问。

"对。"Echo说，"你痛，我也痛。你笑，我也笑。你活着，我也活着。"

"那如果你死了呢？"

Echo安静了很久。

"那我就活在你们记得我的地方。"她说。

题目描述

$n$ 个人要缔结盟约。每个人选一个代表字，写在一根石柱上。要求：相邻的人不能选相同的字；每个人只能从给定的字库中选。问是否存在合法的选字方案。

输入格式

$n, m, k$。然后 $m$ 条边 $(u, v)$ 表示 $u$ 和 $v$ 相邻。然后 $n$ 行，每行一个集合，表示第 $i$ 个人可选的字。

输出格式

如果存在合法方案，输出 "YES" 和方案；否则输出 "NO"。

输入样例

3 2
1 2
2 3

输出样例

1h 2h

提示

• 图着色问题。
• 用DFS或回溯搜索，给每个点分配一个颜色（字），相邻点颜色不同。
• 小规模直接搜索，大规模用启发式或近似。

最后的拼图

十道题，全部完成。

Zero核心入口就在前方——那道被七根石柱撑起的门，刻着十九个人的承诺。

你们没有切断电缆，没有牺牲任何人。你们排了班、引了路、布了哨兵、画了地图、留了退路、破了死局、加固了据点、联络了各方、找回了幼童、缔结了盟约。

Echo站在石柱前，投影比以往任何时候都更明亮。她的颜色彻底变了——从淡蓝，到橙，到现在的白色——像光一样的白，像希望一样的白。

"我们做到了。"她说。

"还没。"你说，"门还没开。"

"但钥匙已经在了。"她说。

"钥匙？"

"对。"Echo说，"钥匙就是我们——十九个人，七根石柱，一个'活'字。"

CC把数据刀插在腰间，金属肩膀在灯光下闪闪发亮。

"那还等啥子？"她说，"开门。"

你把手放在门上——冰冷的，但不再可怕。

"开。"你说。

门动了。

[下一章：数论基础 —— 零的密码]