问题4397--加油

4397: 加油

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的节点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2i-1个结点;深度为k的二叉树至多有2k-1个结点;对任何一棵二叉树T,如果其终端结点树为n0,度为2的节点数为n2n0=n2+1。一棵深度为k,且有2k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1n的节点对应时,称之为完全二叉树。现在qiaoak手里有一副无向图,qiaoak打算考考chenthreeqiaoak的问题是,这幅图是否可以删除一些边(删除边后整幅图仍然联通)使得其变成一棵高度为h的满二叉树。Chenthree陷入了沉思。嗯,这题很简单,大家加油吧。

输入

多组测试数据,第一行输入一个整数T,表示组数

接下来输入两个正整数h,m,表示满二叉树的高度以及边的数量

接下来m行每行两个正整数xiyi分别表示图中相邻的两个节点,可以自己跟自己相邻。

输出

对于每组数据,输出“Correct”如果可以变成满二叉树

输出“Incorrect”如果不能变成满二叉树

样例输入 Copy

1
2 3
1 2
1 3
2 3

样例输出 Copy

Correct

提示

 h<=10,T<=10

m<=2h+2

1<=xi yi<=2h-1

来源/分类