U658543 寻隐者不遇
题目背景
松下问童子,言师采药去。
只在此山中,云深不知处。
——贾岛《寻隐者不遇》
题目描述
贾岛想要到山中求见隐者,却只看到了隐者的徒弟,也就是故事中的童子。童子也不知道隐者的位置,但他给出了如下线索:
山中有 $n$ 个采药点,这些采药点依次编号为 $1 \sim n$ 采完每个采药点的药后可以选择接下来的与该采药点相接的两个采药点中的一个,每次移动花费 1 个单位时间。保证除第 1 个采药点外,其余采药点只能由唯一的一个采药点直接到达。
童子告诉了贾岛从第 1 个采药点开始,每个采药点可以到达的两个采药点,并给出隐者从第 1 个采药点开始,已经采药了 $t$ 个单位时间,贾岛发现采药点的集合可以视作一颗完全二叉树,并希望根据这些信息缩小查找范围。请你帮助贾岛依据上述信息给出可能的隐者位置的编号。
输入格式
输入共 $n+1$ 行。
第 $1$ 行输入两个整数 $n$ 和 $t$。
随后 $n$ 行,第 $i+1$ 行输入两个整数,代表第 $i$ 个采药点可以直接通往的两个采药点的编号,可视为节点的左子节点和右子节点。若输入的编号为 $0$,代表此处无采药点可以通往。
输出格式
输出 $x$ 行($x$ 代表结果找到的可能的隐者位置的个数)。
每行输出一个整数,代表可能的隐者位置。按编号升序输出。
说明/提示
对于 $100\%$ 的数据,$1 \leq n \leq 1000 $,$0 \leq t \leq d - 1$($d$ 代表构造出的完全二叉树的层数)。
题目保证数据一定能够构造出一颗完全二叉树。输入顺序自上而下。