Logical quantifiers are very useful tools for expressing claims about a set. For this problem, let's focus on the set of real numbers specifically. The set of real numbers includes zero and negatives. There are two kinds of quantifiers: universal ($\forall$) and existential ($\exists$). You can read more about them here.

The universal quantifier is used to make a claim that a statement holds for all real numbers. For example:  $\forall x,x<100$ is read as: for all real numbers $x$, $x$ is less than $100$. This statement is false.  $\forall x,x>x-1$ is read as: for all real numbers $x$, $x$ is greater than $x-1$. This statement is true. 

The existential quantifier is used to make a claim that there exists some real number for which the statement holds. For example:  $\exists x,x<100$ is read as: there exists a real number $x$ such that $x$ is less than $100$. This statement is true.  $\exists x,x>x-1$ is read as: there exists a real number $x$ such that $x$ is greater than $x-1$. This statement is true. 

Moreover, these quantifiers can be nested. For example:  $\forall x,\exists y,x<y$ is read as: for all real numbers $x$, there exists a real number $y$ such that $x$ is less than $y$. This statement is true since for every $x$, there exists $y=x+1$.  $\exists y,\forall x,x<y$ is read as: there exists a real number $y$ such that for all real numbers $x$, $x$ is less than $y$. This statement is false because it claims that there is a maximum real number: a number $y$ larger than every $x$. 

Note that the order of variables and quantifiers is important for the meaning and veracity of a statement.

There are $n$ variables $x_1,x_2,\ldots,x_n$, and you are given some formula of the form $$ 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}), $$

where $\land$ denotes logical AND. That is, $f(x_1,\ldots, x_n)$ is true if every inequality $x_{j_i}<x_{k_i}$ holds. Otherwise, if at least one inequality does not hold, then $f(x_1,\ldots,x_n)$ is false.

Your task is to assign quantifiers $Q_1,\ldots,Q_n$ to either universal ($\forall$) or existential ($\exists$) so that the statement $$ Q_1 x_1, Q_2 x_2, \ldots, Q_n x_n, f(x_1,\ldots, x_n) $$

is true, and the number of universal quantifiers is maximized, or determine that the statement is false for every possible assignment of quantifiers.

Note that the order the variables appear in the statement is fixed. For example, if $f(x_1,x_2):=(x_1<x_2)$ then you are not allowed to make $x_2$ appear first and use the statement $\forall x_2,\exists x_1, x_1<x_2$. If you assign $Q_1=\exists$ and $Q_2=\forall$, it will only be interpreted as $\exists x_1,\forall x_2,x_1<x_2$.


-----Input-----

The first line contains two integers $n$ and $m$ ($2\le n\le 2\cdot 10^5$; $1\le m\le 2\cdot 10^5$) — the number of variables and the number of inequalities in the formula, respectively.

The next $m$ lines describe the formula. The $i$-th of these lines contains two integers $j_i$,$k_i$ ($1\le j_i,k_i\le n$, $j_i\ne k_i$).


-----Output-----

If there is no assignment of quantifiers for which the statement is true, output a single integer $-1$.

Otherwise, on the first line output an integer, the maximum possible number of universal quantifiers.

On the next line, output a string of length $n$, where the $i$-th character is "A" if $Q_i$ should be a universal quantifier ($\forall$), or "E" if $Q_i$ should be an existential quantifier ($\exists$). All letters should be upper-case. If there are multiple solutions where the number of universal quantifiers is maximum, print any.


-----Examples-----
Input
2 1
1 2

Output
1
AE

Input
4 3
1 2
2 3
3 1

Output
-1

Input
3 2
1 3
2 3

Output
2
AAE



-----Note-----

For the first test, the statement $\forall x_1, \exists x_2, x_1<x_2$ is true. Answers of "EA" and "AA" give false statements. The answer "EE" gives a true statement, but the number of universal quantifiers in this string is less than in our answer.

For the second test, we can show that no assignment of quantifiers, for which the statement is true exists.

For the third test, the statement $\forall x_1, \forall x_2, \exists x_3, (x_1<x_3)\land (x_2<x_3)$ is true: We can set $x_3=\max\{x_1,x_2\}+1$.

Difficulty: HARD

Starter code:

Solutions:
import sys
(n, m) = [int(x) for x in input().split()]
adj_for = [[] for _ in range(n)]
adj_back = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(x) for x in sys.stdin.readline().split()]
	a -= 1
	b -= 1
	adj_for[a].append(b)
	adj_back[b].append(a)
lens = [len(adj_back[i]) for i in range(n)]
stack = [x for x in range(n) if lens[x] == 0]
toposort = [x for x in range(n) if lens[x] == 0]
while len(stack):
	cur = stack.pop()
	for nb in adj_for[cur]:
		lens[nb] -= 1
		if lens[nb] == 0:
			toposort.append(nb)
			stack.append(nb)
if len(toposort) != n:
	print(-1)
	return
min_above = list(range(n))
min_below = list(range(n))
for i in toposort:
	for j in adj_back[i]:
		if min_above[j] < min_above[i]:
			min_above[i] = min_above[j]
for i in reversed(toposort):
	for j in adj_for[i]:
		if min_below[j] < min_below[i]:
			min_below[i] = min_below[j]
qt = ['A' if min_below[i] == min_above[i] == i else 'E' for i in range(n)]
print(len([x for x in qt if x == 'A']))
print(''.join(qt))


import collections
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
ans = [''] * (n + 1)
g1 = [[] for _ in range(n + 1)]
g2 = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	g1[a].append(b)
	g2[b].append(a)
	deg[a] += 1
status = [0] * (n + 1)
q = collections.deque()
for i in range(1, n + 1):
	if deg[i] == 0:
		q.append(i)
while len(q) != 0:
	v = q.pop()
	status[v] = 1
	for u in g2[v]:
		deg[u] -= 1
		if deg[u] == 0:
			q.append(u)
if status.count(0) >= 2:
	print(-1)
else:
	status1 = [0] * (n + 1)
	status2 = [0] * (n + 1)
	for i in range(1, n + 1):
		if status1[i] == 0 and status2[i] == 0:
			ans[i] = 'A'
		else:
			ans[i] = 'E'
		if status1[i] == 0:
			q = collections.deque()
			q.append(i)
			while len(q) != 0:
				v = q.pop()
				status1[v] = 1
				for u in g1[v]:
					if status1[u] == 0:
						status1[u] = 1
						q.append(u)
		if status2[i] == 0:
			q = collections.deque()
			q.append(i)
			while len(q) != 0:
				v = q.pop()
				status2[v] = 1
				for u in g2[v]:
					if status2[u] == 0:
						status2[u] = 1
						q.append(u)
	print(ans.count('A'))
	print(''.join(map(str, ans[1:])))


import os
import sys
if os.path.exists('/mnt/c/Users/Square/square/codeforces'):
	f = iter(open('E.in').readlines())

	def input():
		return next(f)
else:
	input = sys.stdin.readline
(n, m) = map(int, input().split())
g = {i: [] for i in range(1, n + 1)}
r = {i: [] for i in range(1, n + 1)}
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	r[v].append(u)
mincomp = list(range(n + 1))
try:
	for gr in [g, r]:
		color = [0] * (n + 1)
		for i in range(1, n + 1):
			if color[i] == 0:
				s = [i]
				while s:
					u = s[-1]
					if color[u] == 0:
						color[u] = 1
						for v in gr[u]:
							if color[v] == 0:
								s.append(v)
								mincomp[v] = min(mincomp[u], mincomp[v])
							elif color[v] == 1:
								raise RuntimeError
					elif color[u] == 1:
						color[u] = 2
						u = s.pop()
					elif color[u] == 2:
						s.pop()
	print(sum([u <= mincomp[u] for u in range(1, n + 1)]))
	print(''.join(['A' if u <= mincomp[u] else 'E' for u in range(1, n + 1)]))
except RuntimeError:
	print(-1)


import sys

def input():
	return sys.stdin.readline().rstrip()
from collections import deque

def find_loop(n, e, flag):
	x = [0] * n
	d = deque()
	t = []
	c = 0
	for i in range(n):
		for j in e[i]:
			x[j] += 1
	for i in range(n):
		if x[i] == 0:
			d.append(i)
			t.append(i)
			c += 1
	while d:
		i = d.popleft()
		for j in e[i]:
			x[j] -= 1
			if x[j] == 0:
				d.append(j)
				t.append(j)
				c += 1
	if c != n:
		print(-1)
		exit()
	return t
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
redge = [[] for _ in range(n)]
into = [0] * n
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	into[b] += 1
	edge[a].append(b)
	redge[b].append(a)
dag = find_loop(n, edge, 0)
mi = list(range(n))
for node in dag[::-1]:
	for mode in redge[node]:
		mi[mode] = min(mi[node], mi[mode])
ans = ['E'] * n
visited = [0] * n
for i in range(n):
	if visited[i] == 0:
		stack = [i]
		ans[i] = 'A'
		visited[i] = 1
		for node in stack:
			for mode in edge[node]:
				if visited[mode]:
					continue
				visited[mode] = 1
				stack.append(mode)
for i in range(n):
	if i > mi[i]:
		ans[i] = 'E'
print(ans.count('A'))
print(''.join(ans))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G1 = [[] for _ in range(N + 1)]
G2 = [[] for _ in range(N + 1)]
for _ in range(M):
	(x, y) = map(int, input().split())
	G1[x].append(y)
	G2[y].append(x)
lens = [len(G2[i]) for i in range(N + 1)]
stack = [x for x in range(N + 1) if lens[x] == 0 and x != 0]
topo = [x for x in range(N + 1) if lens[x] == 0 and x != 0]
while stack:
	cur = stack.pop()
	for nb in G1[cur]:
		lens[nb] -= 1
		if lens[nb] == 0:
			topo.append(nb)
			stack.append(nb)
if len(topo) != N:
	print(-1)
	sys.exit(0)
R = [0] * (N + 1)
v1 = set()
v2 = set()
c = 0
for s in range(1, N + 1):
	if s in v1 or s in v2:
		R[s] = 'E'
	else:
		R[s] = 'A'
		c += 1
	stack = [s]
	while stack:
		v = stack.pop()
		for u in G1[v]:
			if u in v1:
				continue
			v1.add(u)
			stack.append(u)
	stack = [s]
	while stack:
		v = stack.pop()
		for u in G2[v]:
			if u in v2:
				continue
			v2.add(u)
			stack.append(u)
print(c)
print(''.join(R[1:]))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def from_file(f):
	return f.readline

def build_graph(n, A, reversed=False):
	edges = [[] for _ in range(n)]
	for (i, j) in A:
		i -= 1
		j -= 1
		if reversed:
			(j, i) = (i, j)
		edges[i].append(j)
	return edges

def fill_min(s, edges, visited_dfs, visited, container):
	visited[s] = True
	visited_dfs.add(s)
	for c in edges[s]:
		if c in visited_dfs:
			return -1
		if not visited[c]:
			res = fill_min(c, edges, visited_dfs, visited, container)
			if res == -1:
				return -1
		container[s] = min(container[s], container[c])
	visited_dfs.remove(s)
	return 0

def dfs(s, edges, visited, container):
	stack = [s]
	colors = {s: 0}
	while stack:
		v = stack.pop()
		if colors[v] == 0:
			colors[v] = 1
			stack.append(v)
		else:
			tmp = [container[c] for c in edges[v]]
			if tmp:
				container[v] = min(min(tmp), container[v])
			colors[v] = 2
			visited[v] = True
		for c in edges[v]:
			if visited[c]:
				continue
			if c not in colors:
				colors[c] = 0
				stack.append(c)
			elif colors[c] == 1:
				return -1
	return 0

def iterate_topologically(n, edges, container):
	visited = [False] * n
	for s in range(n):
		if not visited[s]:
			res = dfs(s, edges, visited, container)
			if res == -1:
				return -1
	return 0

def solve(n, A):
	edges = build_graph(n, A, False)
	container_forward = list(range(n))
	container_backward = list(range(n))
	res = iterate_topologically(n, edges, container_forward)
	if res == -1:
		return None
	edges = build_graph(n, A, True)
	iterate_topologically(n, edges, container_backward)
	container = [min(i, j) for (i, j) in zip(container_forward, container_backward)]
	res = sum((1 if container[i] == i else 0 for i in range(n)))
	s = ''.join(['A' if container[i] == i else 'E' for i in range(n)])
	return (res, s)
(n, m) = invr()
A = []
for _ in range(m):
	(i, j) = invr()
	A.append((i, j))
result = solve(n, A)
if not result:
	print(-1)
else:
	print(f'{result[0]}')
	print(f'{result[1]}')


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
revedge = [[] for i in range(n)]
for i in range(m):
	(j, k) = map(int, input().split())
	edge[j - 1].append(k - 1)
	revedge[k - 1].append(j - 1)
deg = [len(revedge[i]) for i in range(n)]
ans = list((v for v in range(n) if deg[v] == 0))
deq = deque(ans)
used = [0] * n
while deq:
	v = deq.popleft()
	for t in edge[v]:
		deg[t] -= 1
		if deg[t] == 0:
			deq.append(t)
			ans.append(t)
if len(ans) != n:
	print(-1)
	exit()
res = 0
potential = [0] * n
revpotential = [0] * n
ans = [''] * n

def bfs(v):
	que = deque([v])
	potential[v] = 1
	while que:
		pos = que.popleft()
		for nv in edge[pos]:
			if not potential[nv]:
				potential[nv] = 1
				que.append(nv)

def revbfs(v):
	que = deque([v])
	revpotential[v] = 1
	while que:
		pos = que.popleft()
		for nv in revedge[pos]:
			if not revpotential[nv]:
				revpotential[nv] = 1
				que.append(nv)
for i in range(n):
	if not potential[i] and (not revpotential[i]):
		ans[i] = 'A'
		res += 1
		bfs(i)
		revbfs(i)
	else:
		ans[i] = 'E'
		bfs(i)
		revbfs(i)
print(res)
print(''.join(ans))


import sys
(n, m, *jk) = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
rev_links = [set() for _ in range(n)]
degrees_in = [0] * n
for (j, k) in zip(jk[0::2], jk[1::2]):
	j -= 1
	k -= 1
	if k not in links[j]:
		degrees_in[k] += 1
		links[j].add(k)
		rev_links[k].add(j)
s = {i for (i, c) in enumerate(degrees_in) if c == 0}
length = 0
while s:
	length += 1
	v = s.pop()
	for u in links[v]:
		degrees_in[u] -= 1
		if degrees_in[u] == 0:
			s.add(u)
if length < n:
	print(-1)
	exit()
ans = ['E'] * n
larger_fixed = [False] * n
smaller_fixed = [False] * n
universal_cnt = 0
for i in range(n):
	if not larger_fixed[i] and (not smaller_fixed[i]):
		ans[i] = 'A'
		universal_cnt += 1
	q = [i]
	while q:
		v = q.pop()
		if larger_fixed[v]:
			continue
		larger_fixed[v] = True
		q.extend((u for u in links[v] if not larger_fixed[u]))
	q = [i]
	while q:
		v = q.pop()
		if smaller_fixed[v]:
			continue
		smaller_fixed[v] = True
		q.extend((u for u in rev_links[v] if not smaller_fixed[u]))
print(universal_cnt)
print(''.join(ans))