← 返回题目列表

Codeforces · 403/E

E. 两棵有根的树

中文机器翻译题面 查看原题

你有两棵有根无向树,每棵都包含 n 个顶点。让我们用 1 到 n 的整数对每棵树的顶点进行编号。每棵树的根位于顶点 1。第一棵树的边缘涂成蓝色,第二棵树的边缘涂成红色。为了简单起见,假设第一棵树是蓝色的,第二棵树是红色的。

如果满足两个条件,则边 {x, y} 对于边 {p, q} 被称为坏边:

1. 边{x, y}的颜色与边{p, q}的颜色不同。
2. 让我们考虑与边 {p, q} 颜色相同的树。顶点 x、y 之一既位于顶点 p 的子树中,又位于顶点 q 的子树中。

在此问题中,您的任务是模拟下面描述的过程。该过程由几个阶段组成:

1. 在每个阶段上,仅删除一种颜色的边缘。
2. 在第一阶段,恰好删除一条蓝色边缘。
3. 假设在第 i 阶段我们删除了边 {u1, v1}, {u2, v2}, ..., {uk, vk}。在第 i + 1 阶段,我们将删除边 {u1, v1} 的所有未删除的坏边,然后删除边 {u2, v2} 的所有未删除的坏边,依此类推,直到到达边 {uk, vk}。

对于删除边缘的每个阶段,确定将在阶段上删除哪些边缘。请注意,坏边的定义始终考虑删除任何边之前的初始树。

输入

第一行包含整数 n (2 ≤ n ≤ 2·105) — 每棵树中的顶点数。

下一行包含 n - 1 个正整数 a2, a3, ..., an (1 ≤ ai ≤ n; ai ≠ i) — 第一棵树的边的描述。数字ai表示第一棵树有一条连接顶点ai和顶点i的边。

下一行包含 n - 1 个正整数 b2, b3, ..., bn (1 ≤ bi ≤ n; bi ≠ i) — 第二棵树的边的描述。数字bi表示第二棵树有一条连接顶点bi和顶点i的边。

下一行包含整数 idx (1 ≤ idx < n) — 在第一阶段删除的蓝色边缘的索引。假设每棵树的边按照输入中给出的顺序用从 1 到 n-1 的数字进行编号。

输出

对于移除边缘的每个阶段,打印其描述。每个描述必须恰好由两行组成。如果这是删除蓝色边缘的阶段,则描述的第一行必须包含单词“蓝色”,否则为单词“红色”。在第二行中,按升序打印此阶段将删除的边缘的索引。

示例

输入 #1

5
1 1 1 1
4 2 1 1
3

输出 #1

Blue
3
Red
1 3
Blue
1 2
Red
2

注意

为了简单起见,我们假设根树的所有边都接收到某个方向,以便所有顶点都可以从顶点 1 到达。然后,顶点 v 的子树是结果有向图中从顶点 v 可以到达的一组顶点(顶点 v 也包含在该集合中)。