3310. QDT

单点时限: 2.0 sec

内存限制: 256 MB

cdm发明一种新的树名为QDT(Quite Different Tree)。

QDT具备以下性质:

  • QDT是一棵树 ($n$ 个点 $n-1$ 条边的无向连通图)
  • QDT任意两个相邻的点的颜色不同,两点相邻指有一条边直接相连

给定一张图,请问这是QDT么?

输入格式

多组输入,每组输入的第一行为 $n,m$ 表示图的点数和边数

接下来一行 $n$ 个数,第 $i$ 个数为 编号为 $i$ 的点的颜色编号 $c_i(1\leq c_i\leq 100)$

接下来 $m$ 行,每行两个数 $u_i,v_i$ 表示这两点之间有一条边 $(1\leq u_i,v_i\leq n)$

保证 $40\%$ 的数据输入一棵树

保证 $1\leq n,m\leq 100$

输出格式

输入中的图为QDT就输出 Is QDT,否则输出 Is not QDT

样例

Input
3 2
1 1 1
1 2
2 3
3 2
1 2 1
1 2
2 3
Output
Is not QDT
Is QDT

24 人解决,41 人已尝试。

28 份提交通过,共有 134 份提交。

5.6 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,10 月前.

最后提交: 6 月,1 周前.

来源: 2017.7.30 少年宫集训 NOIP模拟赛

题目标签