题目描述

给出一个根节点为1的二叉树的每个节点的左右子节点。如果子节点为0，表示左儿子为空。左右子节点均为0，表示该节点是叶子节点。现在我们有$k$种颜色，可以给树上的每个节点染成任意颜色，颜色用1到$k$这$k$个整数表示。需要保证这$k$种颜色，每种颜色至少染在一个节点上。问是否存在一种染色方案使得对这棵二叉树前序遍历和后序遍历得到的颜色序列完全相同？

例如，对于根为1的3个节点的二叉树，1、2和3的颜色分别为3，2，1；并且1号节点的左儿子是2，右儿子是3。那么前序遍历和后序遍历得到的颜色序列分别是：321和213.

题目输入

第一行是一个$T$，表示有$T$组测试样例。

对于每个测试样例的第一行两个数字分别是$n$和$k$。分别表示二叉树节点个数和颜色种类数。接下来$n$行，第$i$行有两个数字$L[i]$和$R[i]$分别表示第$i$号节点的左右儿子节点编号。

题目输出

对于每个测试样例如果可以找到一种满足条件：（1）$k$种颜色每种颜色至少使用一次，（2）前序遍历和后序遍历的颜色序列完全相同；输出1。否则输出0.

样例输入1

2
2 1
0 2
0 0
2 2
0 2
0 0

样例输出1

1
0

样例解释1

对于第一组测试样例，可以将1号节点和2号节点都染成颜色1.

样例输入2

2
3 2
0 3
0 0
2 0
9 4
2 3
4 0
0 5
6 0
0 7
8 0
0 9
0 0
0 0

样例输出2

1
1

样例解释2

第一组测试样例的一种可能染色序列(第i个元素表示第i个节点的颜色）是：[2, 2, 1];

第二组测试样例的一种可能染色序列(第i个元素表示第i个节点的颜色）是：[2,4,3,1,3,4,3,2,2]。

范围说明

一共包含10组测试样例。每组测试样例满足$T \leq 3$。

对于1-3组测试样例保证：$n \leq 10$。 对于4-6组测试样例保证：$n \leq 100$。 对于7-10组测试样例保证：$n \leq 200$。 对于所有的测试样例保证：$1 \leq k \leq n$。并且所给的二叉树是一棵合法的二叉树。