Two Rooted Trees

题意翻译

你有两棵有根树，每棵各有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*10^5）——两棵树分别有的顶点数目。 接下来的一行包含n-1个正整数a2,a3,...,an(1<=ai<=n;ai<>i)，描述第一棵树的边。数字ai意味着第一棵树有一条边连接顶点ai和顶点i。 接下来的又一行包含n-1个正整数b2,b3,...,bn(1<=bi<=n;bi<>i)，描述第二棵树的边。数字ai意味着第二棵树有一条边连接顶点bi和顶点i。 接下来的再一行包含一个整数idx（1 <=idx < n）表示在第一阶段中删除的边的编号。我们让每棵树的每条边按照他们在输入中的前后顺序从1 到n-1 编号。 输出：对于每个阶段输出两行。如果这个阶段删除的边是蓝色的，那么对应这一阶段的两行中，第一行必须为单词Blue，否则为单词Red。对应的第二行包含所有此阶段删除的边的编号，按数字递增顺序输出。

题目描述

You have two rooted undirected trees, each contains $ n $ vertices. Let's number the vertices of each tree with integers from $ 1 $ to $ n $ . The root of each tree is at vertex $ 1 $ . The edges of the first tree are painted blue, the edges of the second one are painted red. For simplicity, let's say that the first tree is blue and the second tree is red. Edge $ {x,y} $ is called bad for edge $ {p,q} $ if two conditions are fulfilled: 1. The color of edge $ {x,y} $ is different from the color of edge $ {p,q} $ . 2. Let's consider the tree of the same color that edge $ {p,q} $ is. Exactly one of vertices $ x $ , $ y $ lies both in the subtree of vertex $ p $ and in the subtree of vertex $ q $ . In this problem, your task is to simulate the process described below. The process consists of several stages: 1. On each stage edges of exactly one color are deleted. 2. On the first stage, exactly one blue edge is deleted. 3. Let's assume that at the stage $ i $ we've deleted edges $ {u_{1},v_{1}} $ , $ {u_{2},v_{2}} $ , $ ... $ , $ {u_{k},v_{k}} $ . At the stage $ i+1 $ we will delete all undeleted bad edges for edge $ {u_{1},v_{1}} $ , then we will delete all undeleted bad edges for edge $ {u_{2},v_{2}} $ and so on until we reach edge $ {u_{k},v_{k}} $ . For each stage of deleting edges determine what edges will be removed on the stage. Note that the definition of a bad edge always considers the initial tree before it had any edges removed.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 2<=n<=2·10^{5} $ ) — the number of vertices in each tree. The next line contains $ n-1 $ positive integers $ a_{2},a_{3},...,a_{n} $ ( $ 1<=a_{i}<=n; a_{i}≠i $ ) — the description of edges of the first tree. Number $ a_{i} $ means that the first tree has an edge connecting vertex $ a_{i} $ and vertex $ i $ . The next line contains $ n-1 $ positive integers $ b_{2},b_{3},...,b_{n} $ ( $ 1<=b_{i}<=n; b_{i}≠i $ ) — the description of the edges of the second tree. Number $ b_{i} $ means that the second tree has an edge connecting vertex $ b_{i} $ and vertex $ i $ . The next line contains integer $ idx $ ( $ 1<=idx&lt;n $ ) — the index of the blue edge that was removed on the first stage. Assume that the edges of each tree are numbered with numbers from $ 1 $ to $ n-1 $ in the order in which they are given in the input.

输出格式

For each stage of removing edges print its description. Each description must consist of exactly two lines. If this is the stage when blue edges are deleted, then the first line of the description must contain word $ Blue $ , otherwise — word $ Red $ . In the second line print the indexes of the edges that will be deleted on this stage in the increasing order.

输入输出样例

输入样例 #1

5
1 1 1 1
4 2 1 1
3

输出样例 #1

Blue
3
Red
1 3
Blue
1 2
Red
2

说明

For simplicity let's assume that all edges of the root tree received some direction, so that all vertices are reachable from vertex $ 1 $ . Then a subtree of vertex $ v $ is a set of vertices reachable from vertex $ v $ in the resulting directed graph (vertex $ v $ is also included in the set).