3310. QDT

单点时限: 2.0 sec

内存限制: 256 MB

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

QDT具备以下性质:

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

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

输入格式

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

接下来一行 个数,第 个数为 编号为 的点的颜色编号

接下来 行,每行两个数 表示这两点之间有一条边

保证 的数据输入一棵树

保证

输出格式

输入中的图为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

23 人解决,40 人已尝试。

27 份提交通过,共有 132 份提交。

8.2 EMB 奖励。

创建: 2 年,3 月前.

修改: 2 年,2 月前.

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

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

题目标签