在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的节点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2i-1个结点;深度为k的二叉树至多有2k-1个结点;对任何一棵二叉树T,如果其终端结点树为n0,度为2的节点数为n2,则n0=n2+1。一棵深度为k,且有2k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。现在qiaoak手里有一副无向图,qiaoak打算考考chenthree,qiaoak的问题是,这幅图是否可以删除一些边(删除边后整幅图仍然联通)使得其变成一棵高度为h的满二叉树。Chenthree陷入了沉思。嗯,这题很简单,大家加油吧。
多组测试数据,第一行输入一个整数T,表示组数
接下来输入两个正整数h,m,表示满二叉树的高度以及边的数量
接下来m行每行两个正整数xi,yi分别表示图中相邻的两个节点,可以自己跟自己相邻。
对于每组数据,输出“Correct”如果可以变成满二叉树
输出“Incorrect”如果不能变成满二叉树
1
2 3
1 2
1 3
2 3
Correct