Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题面

一天小 $\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$ 代表图中一条边。

输出格式

一行一个字符串 ACWA ,若对于所有 $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 分) 为样例