Tree Edit Distance

Time limit2sMemory limit256 MB

Summary

Compute the minimum leaf insertions, leaf deletions, and relabels that turn one ordered labeled tree into another.

Level: Hard9 of 10
Topics: Dynamic programming, Tree
Solved: No attempts yet

Problem

An XML document holds hierarchically structured data, so it is usually modeled as an ordered labeled tree. One node of the tree corresponds to one XML element, and the label of the node is the tag name of that element. One edge represents the relation between a parent element and a child element. Measuring how similar two XML documents are in structure is a common problem in information retrieval. This problem asks for the structural similarity of two XML documents represented as ordered labeled trees.

Let $T$ be a rooted tree with one or more nodes. If every node carries a label, $T$ is a labeled tree. Labels may repeat. If the children of every node have a fixed left to right order, $T$ is an ordered tree.

The similarity of two ordered labeled trees $T_1$ and $T_2$ is often measured by the tree edit distance $TED(T_1, T_2)$ , the smallest number of edit operations that turn $T_1$ into $T_2$ . Three edit operations can be applied to a tree $T$ .

$Insert(x)$ : insert one leaf whose label is $x$ . If its parent had $d$ children before the operation, the new node becomes the $i$ -th child of that parent for some $i$ with $1 \le i \le d + 1$ .
$Delete()$ : delete one leaf. This operation cannot be applied to a tree with a single node.
$Relabel(x, y)$ : replace the label $x$ of one node by the label $y$ .

Exactly one node is inserted, deleted, or relabeled by one edit operation.

Consider the two trees in Figure 1. Applying $Delete()$ to the leaf labeled C in $T_1$ , then $Relabel(C, E)$ , then $Insert(F)$ turns $T_1$ into $T_2$ . Two or fewer operations cannot turn $T_1$ into $T_2$ , so $TED(T_1, T_2)$ is 3.

(a) $T_1$ (b) $T_2$

Figure 1. Two ordered labeled trees

Write a program that computes the tree edit distance of two given ordered labeled trees.

Input

The first line contains the number of test cases $T$ . Each test case consists of two lines. The first line holds the representation of $T_1$ and the second line holds the representation of $T_2$ .

A tree is written as follows. A tree that consists of a single root node with label $l$ is written as $(l)$ . A tree whose root has label $l$ and whose subtrees are $S_1, S_2, \ldots, S_d$ from left to right is written as $(l(r_1)(r_2)\cdots(r_d))$ , where $(r_1), (r_2), \ldots, (r_d)$ are the representations of $S_1, S_2, \ldots, S_d$ .

Every node label is one uppercase letter of the English alphabet. A representation contains no spaces, and the number of nodes in each tree is between 1 and 1,000.

Output

For each test case, print on one line the minimum number of edit operations that turn $T_1$ into $T_2$ .

Examples3

Example 1

Input

3
(A(B(C)(D))(C(D)))
(A(B(D))(E(D)(F)))
(X(Y(Z(W))))
(W)
(P(P)(P)(P)(P)(P))
(Q(Q)(Q)(Q)(Q))

Expected output

3
4
6

Example 2

Input

4
(A)
(A)
(A)
(B)
(A(B)(C))
(A(B)(C))
(Z)
(Z(Z))

Expected output

Example 3

Input

3
(A(B(C)))
(A(C))
(A(B(C(D))))
(A(D))
(A(B(C))(D))
(A(C)(D))

Expected output

2
3
2