Description

The story takes place in Italy in the year 1486. Ezio was originally a nobleman of the Renaissance. Later, after members of his family were killed by the Templars, he decided to become an assassin. In the end, with his effort and outstanding talent, he became an excellent Master Assassin. He was not only agile and skilled in martial arts, but also good at all kinds of assassination techniques such as parkour across rooftops. Under his leadership, the assassin brotherhood stood up for the oppressed common people and drove away the original ruler of Italy—the leader of the Templars, Pope Alexander VI. In his lifetime, he experienced countless thrilling adventures and assassinations.

Once, in order to find the clues and equipment left by Altair, Ezio explored an assassin tomb in Florence. This tomb has many secret rooms, and between any two rooms there is exactly one unique path. Each room has an assassin mark that he can turn on or off. To open the vault storing the clues and equipment, Ezio must operate the marks to lift an ancient seal. To break this seal, he needs to change the on/off state of some marks so that all marks “look the same” as the password.

Here, “look the same” means: there exists a one-to-one correspondence between the rooms in the “mark” configuration and the rooms in the “password” configuration such that both the connections between rooms and the on/off states match (there is a more detailed explanation in the Hint). Fortunately, before Ezio arrived at the tomb, with the help of Da Vinci, he had already learned the required password to open the vault.

Your task is to help Ezio find the minimum number of mark changes required to achieve the goal.

Input Format

• Line 1: An integer n, the number of rooms.
• Lines 2 to n: Each line contains two integers a and b, indicating there is a passage between room a and room b.
• Line n+1: n integers, giving the current on/off state of each room (0 means off, 1 means on).
• Line n+2: n integers, giving the on/off state of each room in the password.

Output Format

Output a single line: the minimum number of mark changes.

4
1 2
2 3
3 4
0 0 1 1
1 0 0 0

1

Hint

The room numbering can be changed. After turning off the third room in the current configuration, there exists a correspondence between the current marks and the password: 1 -> 4, 2 -> 3, 3 -> 2, 4 -> 1. After renumbering, the connections do not change, and the marks match the password.

In the general case, there exists a permutation P of 1 to n such that for any road u - v between rooms in the current configuration, there is a road P(u) - P(v) in the password configuration; and if there is no road u - v in the current configuration, then there is no road P(u) - P(v) in the password configuration.

Constraints: For 100% of the testdata, $n \le 700$, and each room is adjacent to at most $11$ rooms.

Translated by ChatGPT 5