P15447 「IXOI R1」柚社子

[NATO](https://www.luogu.com.cn/user/443649) 是柚社子的忠实粉丝。 寒假要来了，他计划在寒假玩完一系列柚社子的游戏。这些游戏构成若干有根树形结构。

**注：本题输入输出量较大，请选择合适的输入输出方式。** 给出一个由 $n$ 个点构成的有根树森林，第 $i$（$1\le i \le n$）个点在有根树上的父亲是 $x_i$（若 $x_i=0$ 则表示他是某棵树的根）。 对于每棵树，都会给出一对参数 $(l_a,r_a)$，其中 $a$ 是这棵树的根。 现在你要选取若干个点，并将点的编号组成一个序列，定义一个合法的序列为： - 对于每个满足 $x_a=0$ 的点 $a$，以他为根的树中选取的点的个数在 $[l_a,r_a]$ 之间。 - 对于每一个被选取的点，如果他是根或他的所有祖先中没有点被选，那么没有限制；否则至少有一个他的祖先在序列上的位置在他后面（若这个点在序列的位置为 $i$，则存在一个他的祖先在序列的位置为 $j$，其中 $i

第一行一个正整数 $n$，表示点数。 接下来 $n$ 行，第 $i+1$（$1\le i\le n$）行一至三个整数，第一个整数 $x_i$，表示点 $i$ 在森林上的父亲。若 $x_i=0$，后面紧跟两个由空格隔开的正整数 $[l_i,r_i]$，其意义已在题目描述中给出。

输出两行。 第一行一个整数 $m$，表示字典序最小的序列长度。 第二行 $m$ 个由空格隔开的整数，描述字典序最小的序列。 可以证明在题目的限制下，一定是存在至少一个合法序列的。

### 样例解释 最小的满足条件的字典序是 $2,1,4$，长度为 $3$，可以证明没有字典序更小的方案。 ### 数据范围 **本题采用捆绑测试。** |子任务编号|$n\le$ |特殊性质|分值 | |:---:|:--------:|:--:|:--:| |$0$ |$20$ |无 |$10$| |$1$ |$5\times 10^3$|无 |$20$| |$2$ |$5\times 10^5$ |A |$10$| |$3$ |$5\times 10^5$ |B |$30$| |$4$ |$5\times 10^5$ |无 |$30$| 特殊性质 A：保证每棵树是一个菊花，即每颗树至多有一个点度数超过 $1$，且所有度数大于 $1$ 的点 $i$ 均满足 $x_i=0$。 特殊性质 B：保证 $\forall i,l_i=r_i$。 对于所有数据，保证： $1\le n\le 5\times 10^5$，$\forall x_i,0\le x_i\le n$，保证对于任意一颗树的 $[l,r]$ 满足 $1\le l\le r\le sz$，其中 $sz$ 指对应树的结点数，保证输入的图是一个森林。