给定一棵有 个节点的无向树，节点编号分别为 到 。定义一次 “树上跳点” 操作为：选择一个距离当前点最远的点，并移动过去。如果存在多个满足条件的点，则可以任选一个。 可爱的草莓酱将从 号节点出发，进行恰好 次 “树上跳点” 操作。 你需要对于每个节点分别求解：在这 次操作后，草莓酱是否可能恰好位于该节点上。 【名词解释】 距离：在树中，两个节点之间的距离定义为它们之间最短路径上的边数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入两个整数 ，表示树的节点数、“树上跳点” 操作次数。此后 行，第 行输入两个整数 ，表示树上第 条边连接节点 和 。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出 个整数 ，其中第 个整数 如果为 ，则表示你认为草莓酱不可能在 次操作后恰好位于节点 ；如果为 ，则表示你认为草莓酱可能在 次操作后恰好位于节点 。