At DoorDash, menus are updated daily and even hourly to keep them up-to-date. Each menu can be regarded as a tree. When the merchant sends the latest menu, calculate how many nodes have changed, been added, or been deleted.

Each node in a tree is represented using the following string format:
"key,value,children"

Here:

• key is the node key.
• value is the node value.
• children is the list of direct child keys separated by |.
• Child keys within the same children list are distinct.
• For a leaf node, children is empty.
• Tree will always be connected. i.e. every node is always reachable from root

Example:

• "a,1,b|c" means node a has value 1 and direct children b and c.
• "f,66," means node f has value 66 and no children.

Assume:

• There are no duplicate node keys within the same tree.
• All key and value strings use only lowercase letters and digits.
• Parent-child relationships are derived from the children lists.
• The order of node strings inside existingTree and newTree does not matter.

Methods

Count Changed Nodes

int countChangedNodes(List<String> existingTree, List<String> newTree)

• existingTree and newTree contain node strings in the format "key,value,children".
• Return the total number of change records.
• A node is counted as changed if it is deleted, added, or its value changes.
• If a node appears in both trees with the same key but under a different immediate parent, treat it as one deleted node and one added node.
• If a node is deleted or added, its descendants are also compared independently, and each deleted or added descendant is counted separately.
• Children are ordered in ascending order of their keys lexicographically.

Print Changes

List<String> printChanges(List<String> existingTree, List<String> newTree)

• Return all changes using the formats below:
• "DELETED:key,value,parentKey"
• "ADDED:key,value,parentKey"
• "UPDATED_VALUE:key,oldValue,newValue,parentKey"
• Use ROOT as the parent key for the root node.
• Return deleted entries first, then added entries, then updated-value entries.
• Within each group, sort lexicographically by key.

Change Rules

• If a node exists in existingTree but not in newTree, it is deleted.
• If a node exists in newTree but not in existingTree, it is added.
• If a node exists in both trees with the same key and same immediate parent, but different value, it is a changed node.
• If a node exists in both trees with the same key and same value, but its immediate parent changes, treat the old node as deleted and the new node as added.
• If a node's immediate parent changes, treat it only as one deleted node and one added node, even if its value also changes. Do not also emit UPDATED_VALUE for that node.
• A node is not considered changed merely because its child list differs. Child-list differences matter only through node additions, deletions, or re-parenting.
• Parent comparison is based only on the immediate parent key, not on higher ancestors.
• The count returned by countChangedNodes is the total number of change records, not the number of distinct keys.

Constraints

• 0 ≤ existingTree.size(), newTree.size() ≤ 100000
• 1 ≤ key.length(), value.length() ≤ 100
• key and value contain only characters in [a-z0-9].
• Each node string is always in the format "key,value,children".
• Each tree has unique keys.
• Each non-root node appears as a child of exactly one parent.
• If a tree is non-empty, it has exactly one root.
• Every child key listed in children must also appear as a node key in the same tree.

Examples

Example 1

Example 2

Example 3

Example 4