题目描述

设 $R(U)$ 是一个属性集 $U$ 上的关系模式，$X$ 和 $Y$ 是 $U$ 的子集。若对于 $R(U)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而在 $Y$ 上的属性值不等,则称“$X$ 函数确定 $Y$”或“$Y$ 函数依赖于 $X$”，记作 $X\to Y$。其中 $X$ 称为这个函数依赖的决定属性集（Determinant）。

解释：如果有函数依赖 $X\to Y$ ，当我们知道 $X$ 的时候，也就知道了 $Y$，也就是 $X$ 能推出 $Y$。另外，可以简单的证明，如果 $X\to Y$，$Y\to Z$，那么可以得到 $X\to Z$。

若关系中的某一属性组的值能唯一的表示一个元组，则称该属性组为超码。若关系中的某一属性组的值能唯一地表示一个元组，而其真子集不行，则称该属性组为候选码。

解释：设有属性集合 $(A,B,C)$ 和函数依赖 $A\to B$ 和 $B\to C$，显然，在已知 $A$ 的情况下，我们能够通过函数依赖得到整个集合的所有属性 $ABC$，那么我们称 $A$ 为超码。当超码的任何一个子集都不是超码的时候，我们称之为候选码。例如 $AB$ 是一个超码，但是不是一个候选码，因为 $A$ 是 $AB$ 的子集，它也是超码。 现在给出属性集合和函数依赖集合 $R(U,F)$，请找出该 $R$ 的候选码。

输入格式

输入文件的第一行为一个整数 $n$ 和 $m$，表示属性集中的属性个数和函数依赖集中的依赖个数。这里我们默认大写字母中的前 $n$ 个字母为我们所考虑的属性。接下来的 $m$ 行每行一个字符串表示一个函数依赖，如 AB->DE。（中间的蕴含符号是由减号和大于号组成。另外需要说明的是，只有当我们同时得到 $A$ 和 $B$ 的时候，才能推出 $D$ 和 $E$）。

输出格式

第一行输出你找到的候选码的个数 $k$。

接下来的 $k$ 行每行输出一个候选码。候选码本身按字母顺序排列，所有候选码按照字典顺序排列输出。如果没有找到候选码，输出 No candidate key。

样例

5 5
AB->C
AC->B
AD->E
BC->D
E->A

4
AB
AC
BE
CE

数据规模与约定

对于 $30\%$ 的测试数据，保证只有二元联系（即不存在函数依赖左边或右边的属性个数超过 $1$ 个）。

对于 $40\%$ 的测试数据，保证 $n\le 5$。

对于 $70\%$ 的测试数据，保证 $m\le 100$。

对于 $100\%$ 的测试数据，保证 $1\le n\le 10,1\le m\le 1000$。

题目来源

Beijing2009 WinterCamp Day1