纯人工翻译

题目描述

你有两棵有根树，每棵树都有 $n$ 个结点。不妨将这两棵树上的点都用 $1$ 到 $n$ 之间的整数编号。每棵树的根结点都是 $1$。第一棵树上的边都是蓝色，第二课树上的边都是红色。我们也称第一棵树是蓝色的，第二棵树是红色的。

对于一条边 $(p, q)$，当以下条件满足时，我们认为 $(x, y)$ 是一条坏边：

• 边 $(x, y)$ 的颜色与 $(p, q)$ 的颜色不同。
• 考虑与 $(p, q)$ 颜色相同的那棵树。在 $x$ 和 $y$ 中有且仅有其中一个点同时位于 $p$ 和 $q$ 的子树。（注意这里的 $x, y$ 和上面的 $(x, y)$ 不在同一棵树上）

在本题中，你的任务是模拟下述过程。该过程包含几个阶段：

• 在每个阶段，有且仅有一种颜色的边可以被删除。
• 在第 $1$ 个阶段，有且仅有一条蓝色的边被删除。
• 假设在第 $i$ 个阶段我们删除了 $(u_1, v_1), (u_2, v_2), ..., (u_k, v_k)$。在第 $i+1$ 个阶段，我们会先删除所有对于 $(u_1, v_1)$ 的没有删除的坏边，然后删除所有对于 $(u_2, v_2)$ 的没有删除的坏边，然后一直进行下去，直到 $(u_k, v_k)$ 结束。

对于每一个阶段，输出哪些边会被删除。注意，对于一条边的坏边的定义，我们总是只考虑初始的那两棵树。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 2 \times 10^5)$，表示一棵树上点的个数。

接下来一行包含 $n-1$ 个正整数 $a_2, a_3, ..., a_n (1 \leq a_i \leq n; a_i \leq i)$，用来描述第一棵树。其中，$a_i$ 表示第一棵树上存在一条边连接了 $a_i$ 和 $i$。

接下来一行包含 $n-1$ 个正整数 $b_2, b_3, ..., b_n (1 \leq b_i \leq n; b_i \leq i)$，用来描述第二棵树。其中，$a_i$ 表示第二棵树上存在一条边连接了 $b_i$ 和 $i$。

接下来一行包含一个整数 $idx$，表示第一阶段所删除的蓝色边的编号。假设每棵树的边都按照输入顺序从 $1$ 到 $n-1$ 编号。

输出格式

对于每一个删边的阶段，输出两行。如果在一个删除蓝色边的阶段，那么第一行输出一个单词 Blue，否则输出 Red。第二行按升序输出，此阶段被删除的所有边的编号。

样例解释

可以自己画一下图，下面给出样例解释。

• 首先删除蓝色 $3$ 号边：$(1, 4)$；
• 在第一棵树上，只有 $4$ 号点满足同时在 $1$ 和 $4$ 的子树上，所以第二棵树上所有与 $4$ 相连的边全部被删除，也就是红色 $1$ 号边：$(2, 4)$ 和红色 $3$ 号边 $(1, 4)$；
• 在第二棵树上，$2, 3$ 号点满足同时在 $2$ 和 $4$ 的子树上，所以第一棵树上所有与 $2$ 或 $3$ 相连的边全部被删除，也就是蓝色 $1$ 号边：$(1. 2)$ 和蓝色 $2$ 号边 $(1, 3)$，至于满足同时在 $1$ 和 $4$ 子树上的点，由于已经被删除干净，所以不提；
• 在第一棵树上，只有 $2$ 号点满足同时在 $1$ 和 $2$ 的子树上，所以第二棵树上所有与 $2$ 相连的边全部被删除，也就是红色 $2$ 号边：$(2. 3)$ ；
• 没有边可以删除，程序结束。