E. Два корневых дерева
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

У вас есть два корневых неориентированных дерева, каждое из которых содержит по 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, a4, ..., an (1 ≤ ai ≤ n; ai ≠ i) — описание ребер первого дерева. Число ai означает, что в первом дереве имеется ребро, соединяющее вершину ai и вершину i.

В следующей строке задано n - 1 целое положительное число b2, b3, b4, ..., bn (1 ≤ bi ≤ n; bi ≠ i) — описание ребер второго дерева. Число bi означает, что во втором дереве имеется ребро, соединяющее вершину bi и вершину i.

В следующей строке задано целое число idx (1 ≤ idx < n) — индекс синего ребра, которое было удалено на первом этапе. Считайте, что ребра каждого дерева пронумерованы числами от 1 до n - 1 в том порядке, в котором они заданы во входных данных.

Выходные данные

Для каждого этапа удаления ребер выведите его описание. Каждое описание должно состоять ровно из двух строк. Если на данном этапе будет происходить удаление синих ребер, тогда в первой строке описания этапа должно содержаться слово Blue, иначе слово Red. Во второй строке выведите индексы ребер, которые будут удалены на данном этапе, в порядке возрастания.

Примеры
Входные данные
5
1 1 1 1
4 2 1 1
3
Выходные данные
Blue
3
Red
1 3
Blue
1 2
Red
2
Примечание

Для удобства представим, что все ребра корневого дерева получили некоторое направление, причем так, что все вершины достижимы из вершины с номером 1. Тогда поддеревом вершины v будем называть множество вершин, достижимых из вершины с номером v в полученном ориентированном графе (сама вершина v тоже входит в это множество).