Assassin Tomb Isomorphism

In 1486 Italy, Ezio Auditore faces one of his toughest challenges. Deep within an ancient assassin tomb, there are many secret chambers (nodes) connected by corridors such that between any two chambers there is exactly one unique path (i.e. the chambers form a tree). Every chamber carries an assassin mark that can be either active (1) or inactive (0). To open the storeroom holding clues and equipment left by Altair, Ezio must adjust the marks so that the configuration of his tomb "appears identical" to a secret password configuration.

The phrase "appears identical" is defined as follows: There exists a one‐to‐one correspondence (an isomorphism) between the tomb’s chambers and the password’s chambers such that both the connectivity (i.e. the tree structure) and the activation status (the binary mark) match.

You are given two trees with n nodes. The first tree represents the assassin tomb with its initial mark configuration, and the second tree represents the secret password (its configuration is fixed). Your task is to help Ezio by determining the minimum number of mark state changes (flips) needed on the tomb so that there exists an isomorphism between the two trees mapping each chamber’s mark in the tomb to the corresponding chamber’s mark in the password. Formally, label the nodes of the tomb as 1,2,…,n and let A be a binary string of length n (with characters '0' or '1') giving the initial state. Similarly, label the nodes of the password tree (in an arbitrary order) and let B be its binary string configuration. Because the two trees are unrooted but are known to be isomorphic as graphs, there exists some isomorphism f from the tomb to the password tree. Your goal is to choose an isomorphism f and flip some bits in A (each flip has cost 1) so that:

$$A[u] = B[f(u)] \quad \text{for all nodes } u \in \{1,2,\dots,n\}, $$

and the total number of flips is minimized.

Note: Two trees are isomorphic if there exists a bijection between their nodes preserving adjacency. In this problem, you are allowed to choose any isomorphism between the two trees. It might be beneficial to “swap” symmetrical subtrees if the initial configuration makes some mismatches which can be avoided under a different isomorphism.

inputFormat

The input consists of the following parts:

1. An integer n (1 ≤ n ≤ 15) representing the number of chambers.
2. n-1 lines, each containing two integers u and v (1-based indices) describing an edge in the tomb tree.
3. A binary string of length n (each character is either '0' or '1') representing the initial state of the tomb’s marks.
4. n-1 lines, each containing two integers u and v describing an edge in the password tree.
5. A binary string of length n representing the password configuration of marks.

You may assume that both trees are connected and that there is exactly one unique simple path between any two nodes.

outputFormat

Output a single integer, the minimum number of flips required for the tomb’s configuration to be isomorphic to the password configuration. If no isomorphism exists (which will not happen in the test cases), output -1.

sample

1


0



1

1