逻辑量词是表达集合声明的非常有用的工具。对于这个问题,我们专门关注实数集。实数集包括零和负数。量词有两种:通用量词 ($$$\forall$$$) 和存在量词 ($$$\exists$$$)。您可以在这里阅读有关它们的更多信息。
全称量词用于声明某个陈述对所有实数都成立。例如:
- $$$\forall x,x<100$$$ 读作:对于所有实数 $$$x$$$,$$$x$$$ 小于 $$$100$$$。这种说法是错误的。
- $$$\forall x,x>x-1$$$ 读作:对于所有实数 $$$x$$$,$$$x$$$ 大于 $$$x-1$$$。这个说法是正确的。
存在量词用于声明存在该陈述成立的某个实数。例如:
- $$$\exists x,x<100$$$ 读作:存在一个实数 $$$x$$$ 使得 $$$x$$$ 小于 $$$100$$$。这个说法是正确的。
- $$$\exists x,x>x-1$$$ 读作:存在一个实数 $$$x$$$ 使得 $$$x$$$ 大于 $$$x-1$$$。这个说法是正确的。
此外,这些量词可以嵌套。例如:
- $$$\forall x,\exists y,x<y$$$ 读作:对于所有实数 $$$x$$$,存在一个实数 $$$y$$$,使得 $$$x$$$ 小于 $$$y$$$。这个陈述是正确的,因为对于每个$$$x$$$,都存在$$$y=x+1$$$。
- $$$\exists y,\forall x,x<y$$$ 读作:存在一个实数 $$$y$$$,使得对于所有实数 $$$x$$$,$$$x$$$ 小于 $$$y$$$。这个陈述是错误的,因为它声称存在最大实数:一个大于每个 $$$x$$$ 的数字 $$$y$$$。
请注意,变量和量词的顺序对于语句的含义和准确性很重要。
有 $$$n$$$ 变量 $$$x_1,x_2,\ldots,x_n$$$,并给出一些如下形式的公式 $$$$$$ f(x_1,\dots,x_n):=(x_{j_1}<x_{k_1})\land (x_{j_2}<x_{k_2})\land \cdots\land (x_{j_m}<x_{k_m}), $$$$$$
其中 $$$\land$$$ 表示逻辑 AND。也就是说,如果每个不等式 $$$x_{j_i}<x_{k_i}$$$ 成立,则 $$$f(x_1,\ldots, x_n)$$$ 为真。否则,如果至少一个不等式不成立,则 $$$f(x_1,\ldots,x_n)$$$ 为假。
您的任务是将量词 $$$Q_1,\ldots,Q_n$$$ 分配给通用 ($$$\forall$$$) 或存在 ($$$\exists$$$),以便语句 $$$$$$ Q_1 x_1, Q_2 x_2, \ldots, Q_n x_n, f(x_1,\ldots, x_n) $$$$$$
为真,并且全称量词的数量被最大化,或者确定该陈述对于每个可能的量词分配都是假的。
请注意,变量在语句中出现的顺序是固定的。例如,如果 $$$f(x_1,x_2):=(x_1<x_2)$$$ 则不允许首先出现 $$$x_2$$$ 并使用语句 $$$\forall x_2,\exists x_1, x_1<x_2$$$。如果您指定 $$$Q_1=\exists$$$ 和 $$$Q_2=\forall$$$,则只会将其解释为 $$$\exists x_1,\forall x_2,x_1<x_2$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$; $$$1\le m\le 2\cdot 10^5$$$) - 分别是公式中变量的数量和不等式的数量。
接下来的 $$$m$$$ 行描述了该公式。这些行的第 $$$i$$$ 包含两个整数 $$$j_i$$$,$$$k_i$$$ ($$$1\le j_i,k_i\le n$$$, $$$j_i\ne k_i$$$)。
输出
如果没有符合该语句的量词分配,则输出单个整数 $$$-1$$$。
否则,在第一行输出一个整数,即全称量词的最大可能数量。
在下一行中,输出长度为 $$$n$$$ 的字符串,其中如果 $$$Q_i$$$ 应为全称量词 ($$$\forall$$$),则第 $$$i$$$ 个字符为“A”;如果 $$$Q_i$$$ 应为存在量词 ($$$\exists$$$),则输出“E”。所有字母都应为大写。如果存在多个全称量词数量最大的解,则打印任意一个。
示例
输入 #1
2 1 1 2
输出 #1
1 AE
输入 #2
4 3 1 2 2 3 3 1
输出 #2
-1
输入 #3
3 2 1 3 2 3
输出 #3
2 AAE
注意
对于第一个测试,语句 $$$\forall x_1, \exists x_2, x_1<x_2$$$ 为 true。 “EA”和“AA”的答案给出了错误的陈述。答案“EE”给出了正确的陈述,但该字符串中的全称量词数量少于我们的答案。
对于第二个测试,我们可以证明不存在语句为 true 的量词赋值。
对于第三个测试,语句 $$$\forall x_1, \forall x_2, \exists x_3, (x_1<x_3)\land (x_2<x_3)$$$ 为真:我们可以设置 $$$x_3=\max\{x_1,x_2\}+1$$$。