题面

一天小 $\Delta$ 看到了一个题目：

对于一个简单无向图，每个点有一个非负整数权值 $a_i$，每次操作可以选择一个点集的子集 $U$，使得 $U$ 的导出子图连通，然后将 $U$ 中的每个点的 $a_i$ 都减去 $1$，求将所有点 $a_i$ 变为 $0$ 的最小操作次数。

小 $\Delta$ 很快编了一个算法，流程如下：

1. 若图中所有点权值都是 $0$，停止。
2. 选择图中所有 $a_i\neq 0$ 的点中，编号最小的一个点 $u$
3. 构造集合 $U$，其中 $v\in U$ 当且仅当 $u$ 和 $v$ 可以仅经过权值非零的点互相到达。容易发现 $U$ 的导出子图是连通的。
4. 操作集合 $U$
5. 回到第一步。

小 $\Delta$ 写完交了上去，喜提 $\text{WA}$，他立刻意识到自己假了，然后开始和暴搜对拍，但不知道为何拍不出错。他意识到有可能是自己数据造的有特殊性质。经过排查之后，发现生成的图一定是一条链！

将对拍改过来之后，小 $\Delta$ 立刻找到了反例，但他又产生了一个疑惑：当这张图是什么样的时候，这个算法才是对的？他把这个问题交给了你。

具体来讲，给定一个简单无向图，你需要判断是否存在一个初始权值 $a_i$，使得小 $\Delta$ 给出的算法的操作次数不是最优的。你不必输出方案。

输入格式

第一行，两个非负整数 $n,m$ 代表图的点数和边数。 接下来 $m$ 行，每行两个正整数 $u,v$ 代表图中一条边。

输出格式

一行一个字符串 AC 或 WA ，若对于所有 $a_i$ ，小 $\Delta$ 的算法都是正确的，输出 AC，否则输出 WA

样例 1

输入

3 2
1 2
2 3

输出

AC

样例 2

输入

4 4
1 2
2 3
3 4
4 1

输出

WA

解释

当 $a_1=a_3=1,a_2=a_4=2$ 时，小 $\Delta$ 的算法使用 $3$ 次操作，而最优方案仅需 $2$ 次。

样例 3

见下发文件，此样例满足子任务 1 的限制。

样例 4

见下发文件，此样例满足子任务 1 的限制。

样例 5

见下发文件，此样例满足子任务 3 的限制。

样例6

见下发文件，此样例满足子任务 4 的限制。

样例 7

见下发文件，此样例满足子任务 5 的限制。

数据范围与限制

对于所有数据 $1\leq n\leq 10^5,0\leq m\leq 10^6$ ，保证给定的图是简单图。

子任务如下：

1. (10 分) $n \leq 5$
2. (20 分) $n \leq 10$
3. (5 分) 保证图连通，$m \leq n-1$
4. (10 分) 保证图连通，$m \leq n$
5. (20 分) 保证图连通，$m \leq n+5$
6. (35 分) 无特殊限制
7. (922 分) 为样例