Lowest Common Ancestor Color

You are given a binary tree in which each node has an integer value and a color (either red or blue). Your task is to determine the color of the lowest common ancestor (LCA) of two nodes with given values p and q.

The lowest common ancestor (LCA) of two nodes is defined as the deepest node (i.e. farthest from the root) that has both nodes in its subtree. Formally, if we denote the LCA of nodes p and q as \(\text{LCA}(p, q)\), then for any node \(x\) in the tree, if both p and q are in the subtree of \(x\), then \(\text{depth}(x) \le \text{depth}(\text{LCA}(p, q))\).

The tree is provided as a set of nodes where each node description contains a value, a color, and the indices of its left and right children in the input order (0-indexed, with -1 indicating no child). The first node is the root of the tree.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer n indicating the number of nodes in the tree.
2. n lines follow, each describing a node with four items separated by spaces: value (an integer), color (a string, either red or blue), left_index, and right_index (both integers, with -1 representing a missing child). The nodes are given in order; the node on the first line is the root.
3. A final line with two integers p and q representing the values of the nodes for which you must compute the LCA color.

outputFormat

Output the color (red or blue) of the lowest common ancestor of the nodes with values p and q to standard output (stdout).

7
1 red 1 2
2 blue 3 4
3 red 5 6
4 blue -1 -1
5 red -1 -1
6 blue -1 -1
7 blue -1 -1
4 5

blue