#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node {
    string Name;
    string Value;
    vector<Node*> childNodes;
};

// Merge two nodes that have the same Name.
// The merged node takes its Value from t2 and its children are merged recursively.
Node* merge(Node* t1, Node* t2) {
    if (!t1 && !t2) return nullptr;
    if (!t1) return t2;
    if (!t2) return t1;

    // Create a new merged node.
    Node* merged = new Node;
    merged->Name = t1->Name;      // (Assumed equal to t2->Name)
    merged->Value = t2->Value;    // Use the value from t2

    vector<Node*> mergedChildren;
    // We'll mark which children in t2 have been used (merged with a t1 child).
    vector<bool> used(t2->childNodes.size(), false);

    // First, go through t1's children in order.
    for (Node* child1 : t1->childNodes) {
        int matchIndex = -1;
        // Look for a matching child in t2 (by Name) that has not yet been used.
        for (int i = 0; i < t2->childNodes.size(); i++) {
            if (!used[i] && t2->childNodes[i]->Name == child1->Name) {
                matchIndex = i;
                break;
            }
        }
        if (matchIndex != -1) {
            // Merge the matching children.
            used[matchIndex] = true;
            Node* mergedChild = merge(child1, t2->childNodes[matchIndex]);
            mergedChildren.push_back(mergedChild);
        } else {
            // No match from t2: include the t1 child as is.
            mergedChildren.push_back(child1);
        }
    }

    // Then, append any unmatched children from t2 (in their original order).
    for (int i = 0; i < t2->childNodes.size(); i++) {
        if (!used[i]) {
            mergedChildren.push_back(t2->childNodes[i]);
        }
    }

    merged->childNodes = mergedChildren;
    return merged;
}

// A helper function to print the tree (for demonstration).
void printTree(Node* root, int depth = 0) {
    if (!root)
        return;
    for (int i = 0; i < depth; i++) cout << "  ";
    cout << root->Name << " : " << root->Value << "\n";
    for (Node* child : root->childNodes)
        printTree(child, depth + 1);
}

int main(){
    // Build an example based on the given sample.
    // Document t1:
    // Root : t1
    // ├── A : alpha
    // │      ├── B : beta
    // │      └── C : Ceta
    // ├── C : xz
    // ├── D : zy
    // └── A : dolce
    Node* t1 = new Node{"Root", "t1", {}};
    Node* A1 = new Node{"A", "alpha", {}};
    Node* B   = new Node{"B", "beta", {}};
    Node* C1  = new Node{"C", "Ceta", {}};
    A1->childNodes.push_back(B);
    A1->childNodes.push_back(C1);
    Node* C2 = new Node{"C", "xz", {}};
    Node* D  = new Node{"D", "zy", {}};
    Node* A2 = new Node{"A", "dolce", {}};
    t1->childNodes.push_back(A1);
    t1->childNodes.push_back(C2);
    t1->childNodes.push_back(D);
    t1->childNodes.push_back(A2);

    // Document t2:
    // Root : t2
    // ├── A : beta
    // │      └── X : lk
    // └── E : theta
    Node* t2 = new Node{"Root", "t2", {}};
    Node* A3 = new Node{"A", "beta", {}};
    Node* X  = new Node{"X", "lk", {}};
    A3->childNodes.push_back(X);
    Node* E  = new Node{"E", "theta", {}};
    t2->childNodes.push_back(A3);
    t2->childNodes.push_back(E);

    // Merge the two documents at the root.
    // We assume the root nodes are merged by merging their children.
    Node* mergedRoot = merge(t1, t2);

    // Print the merged tree.
    printTree(mergedRoot);

    return 0;
}