量词问题

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个按固定顺序出现的实变量 $x_1,x_2,\ldots,x_n$。给定 $m$ 个严格不等式，它们的合取式为

$$f=(x_{j_1}<x_{k_1})\land\cdots\land(x_{j_m}<x_{k_m}).$$

请按变量的固定顺序，为每个变量选择全称量词或存在量词，使量化后的命题为真，并最大化全称量词的数量。变量顺序不能改变。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个不同的整数 $j,k$，表示不等式 $x_j<x_k$。

输出格式

如果不存在合法量词分配，输出一行 -1。

否则，第一行输出全称量词的最大数量；第二行输出一个长度为 $n$ 的字符串，其中 A 表示全称量词，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

数据范围

$2\le n\le2\cdot10^5$，$1\le m\le2\cdot10^5$，$1\le j,k\le n$ 且 $j\ne k$。

子任务编号	分值	特殊限制
1	30	$n\le10$
2		$n\le2000$
3	40	无特殊限制

每个测试点独立计分。