0257. Два дерева

Input file name:	2tree.in
Output file name:	2tree.out
Time limit:	2 s
Memory limit:	256 megabytes

Жюри предлагает участникам олимпиады познакомиться с двоичными деревьями, которые очень широко применяются в программировании.

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

Если вершина Y – ребенок вершины X, то говорят, что вершина X является родителем вершины Y . У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Будем говорить, что два дерева имеют одинаковую структуру, если можно так занумеровать вершины второго дерева, чтобы оно стало идентичным первому.

Примеры двоичных деревьев:

Пусть два двоичных дерева заданы следующим образом: для каждой вершины дерева нам известны номера ее левого и правого детей. Обладая такой информацией, можно однозначно определить корень каждого дерева.

Введем операцию поворота двоичного дерева относительно некоторой вершины.

1. Правый поворот дерева относительно вершины v:

   

2. Левый поворот дерева относительно вершины v:

   

На рисунках прямоугольниками обозначены поддеревья (возможно не содержащие вершин).

Пример левого поворота дерава относительно вершины 2:

Пример правого поворота дерева относительно вершины 3:

С помощью поворотов вершин можно менять структуру дерева. Требуется определить, можно ли из первого дерева получить дерево, структура которого будет такой же, как у второго. Если решение существует, то выведите последовательность поворотов, которые нужно применить к первому дереву.

Формат входного файла

В первой строке входного файла содержится число n – количество вершин у первого и второго деревьев (3 ≤ n ≤ 1000).

Далее следуют 2n строк: в первых n строках идет описание первого дерева, во вторых n – второго дерева.

Описание дерева имеет следующий формат: в i строке описания содержится 2 числа – левый и правый сыновья вершины i. Если какого-то ребенка у вершины нет, то вместо его номера указан 0.

Формат выходного файла

Если решение существует, то в первую строку выходного файла выведите число поворотов m, при этом m не должно превышать 50000. Далее выведите m строк следующего вида: "номер_вершины_первого_дерева поворот", где поворот – это одна из двух строк: "left"(если левый поворот) или "right"(если правый поворот). В случае, если решения не существует, выведите число -1.

Пример:

2tree.in	2tree.out
3 2 3 0 0 0 0 0 0 1 3 0 0	0
7 0 4 1 3 5 6 0 0 7 0 0 0 0 0 0 4 1 5 2 6 0 0 7 0 0 0 0 0	1 2 left
7 0 4 1 3 5 6 0 0 7 0 0 0 0 0 0 4 1 5 0 6 0 0 7 3 0 0 0 0	1 3 right

Source: Командное школьное первенство Республики Карелия по программированию, 4 ноября 2007.

Discuss       Submit a solution



Printable version