The story takes place in Italy in 1486. Ezio was originally just a nobleman of the Renaissance, but after his family members were murdered by the Templars, he became determined to become an assassin. Eventually, through his hard work and exceptional talent, he became an outstanding Master Assassin. He was not only an agile martial arts expert, skilled at scaling walls and performing various assassination techniques, but under his leadership, the Assassin Brotherhood sought justice for the exploited commoners and drove out the leader of the Templars who had ruled Italy, Pope Alexander VI. Throughout his life, he experienced countless thrilling and gripping adventures and assassinations.

Once, in order to find the clues and equipment left behind by Altair, Ezio explored an assassin's tomb in Florence. This tomb contained many secret chambers, and there was a unique path between any two chambers. Each of these chambers contained an assassin's mark, which he could either activate or deactivate. To open the storage room containing the clues and equipment, Ezio had to manipulate the assassin's marks to break an ancient seal. To unlock this seal, he needed to change the activation status of certain marks so that all the assassin's marks "looked the same" as the seal's password.

Here, "looked the same" is defined as: there exists a one-to-one correspondence between the "mark" chambers and the "password" chambers such that the connections between the chambers and their activation statuses are identical (see the hint for a more detailed explanation). Fortunately, before Ezio arrived at the tomb, with the help of Da Vinci, he had already learned the password required to open the storage room.

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

Input

The first line contains an integer $n$, representing the number of secret chambers.

The second to the $n$-th line each contain two integers $a$ and $b$, representing a passage between the $a$-th chamber and the $b$-th chamber.

The $(n+1)$-th line contains $n$ integers, representing the activation status of each chamber at that time (0 for deactivated, 1 for activated).

The $(n+2)$-th line contains $n$ integers, representing the activation status of each chamber in the password.

Output

Output a single line containing the minimum number of mark changes required.

Examples

Input 1

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

Output 1

1

Subtasks

For $30\%$ of the data, $n \leq 10$.

For $60\%$ of the data, $n \leq 100$.

For $100\%$ of the data, $1 \leq n \leq 700$, and each chamber is connected to at most 11 other chambers.