Binary Tree Query Processor

You are given a series of queries to build and query a binary tree. Initially, the tree contains a single node with value 1. You will be asked to:

• Add a new node as a child to an existing node.
• Perform a pre-order traversal of a subtree.
• Determine the maximum depth of a subtree.

The queries are given in one of the following forms:

• A P V: Add a node with value V as a child of the node with value P. If the parent already has two children, the query is ignored.
• P V: Output the pre-order traversal (node values separated by spaces) of the subtree rooted at node V.
• D V: Output the maximum depth of the subtree rooted at node V. The depth of a leaf node is 1.

Note that the maximum depth d of a subtree is defined recursively as:

\(d = \max(d_{\text{left}}, d_{\text{right}}) + 1\)

You need to implement the queries and output the results for the P and D queries in the order they appear.

inputFormat

The input consists of multiple lines. The first line contains an integer N which denotes the number of queries. The next N lines each contain a query in one of the forms described above.

All queries are read from standard input.

outputFormat

For each query of type P or D, output the result on a new line on standard output. For a P query, output the node values in a pre-order traversal separated by a single space. For a D query, output a single integer representing the maximum depth of that subtree.

## sample

6
A 1 2
A 1 3
A 2 4
A 2 5
P 2
D 1

2 4 5
3

</p>