Validate a Binary Tree Built from Directed Edges

You are given a list of directed edges. Each edge is a pair (parent, child) of positive-integer node labels, meaning parent points to child. The set of nodes is exactly the set of labels that appear in at least one edge.

Determine whether the edges form a single valid binary tree:

• Exactly one root (a node with no parent).
• Every non-root node has exactly one parent.
• No node has more than two children.
• There are no cycles, and every node is reachable from the root (equivalently, the edges form one connected tree, not a forest).

If the edges do not form a valid binary tree, output the first error code that applies from the priority list below (check in this exact order and report only the highest-priority error):

1. INVALID_INPUT — some edge is a self-loop (parent == child), or the exact same (parent, child) edge appears more than once.
2. TOO_MANY_CHILDREN — some node appears as the parent in more than two edges.
3. MULTIPLE_PARENTS — some node appears as the child in more than one edge.
4. CYCLE — the edges contain a directed cycle.
5. MULTIPLE_ROOTS — more than one node has no parent (the edges form a forest of two or more trees).

If the edges do form a valid binary tree, output its in-order traversal serialization: visit the left subtree, then the node, then the right subtree, and print the node labels separated by single spaces.

Left/right child rule

Edges are given in a fixed order. For any parent node:

• The first edge listed with that node as parent attaches its left child.
• The second edge listed with that node as parent attaches its right child.
• A node with only one child edge has only a left child.

Input

• edges: a list of pairs [parent, child] of positive integers, in a fixed given order.

Output

Return a single string:

• one of the five error codes above (exactly as spelled, uppercase) if the edges do not form a valid binary tree, or
• the space-separated in-order traversal of the tree if they do.

Examples

Example 1 — valid tree

edges = [[1,2],[1,3],[2,4],[3,5]]

Node 1 has left child 2 and right child 3; node 2 has left child 4; node 3 has left child 5.

Output: 4 2 1 5 3

Example 2 — cycle

edges = [[1,2],[2,3],[3,1]]

Every node has exactly one parent and at most two children, but the edges form a directed cycle.

Output: CYCLE

Example 3 — too many children

edges = [[1,2],[1,3],[1,4]]

Node 1 has three children.

Output: TOO_MANY_CHILDREN

Example 4 — multiple roots

edges = [[1,2],[3,4]]

Nodes 1 and 3 both have no parent, so the edges form a forest.

Output: MULTIPLE_ROOTS

Example 5 — duplicate edge

edges = [[1,2],[1,2]]

The edge (1,2) appears twice.

Output: INVALID_INPUT

Example 6 — multiple parents

edges = [[1,2],[1,3],[2,4],[3,4]]

Node 4 has two parents (2 and 3).

Output: MULTIPLE_PARENTS

Constraints

• 1 <= number of edges <= 10^4
• 1 <= node label <= 10^5
• Node labels within the tree are distinct identifiers; the same label never denotes two different nodes.
• The error priority order must be respected: when several problems exist simultaneously, report only the highest-priority one.