Description

Having to visit the museum day after day as an art critic—and not being allowed to touch the ex-hibits! turned out to be too much for you. Therefore, you decided to give your career as an art thief another try. However, after the total disaster of your debut, you are determined to do something about the surveillance cameras this time.

Accordingly, you have used your IT skills to hack into the camera control system. Unfortunately, the cameras themselves are part of the recent installation artwork Xanadu. This leads to a rather strange behaviour: There are $𝑁$ cameras (numbered $1, \ldots , 𝑁$) distributed over the museum, some of which might already be turned off for artistic reasons. The $𝑁$ cameras are connected by $𝑁 − 1$ wires in such a way that any two of them are connected to each other either directly or indirectly. The camera control system offers a button for each individual camera. However, pressing such a button does not only toggle this single camera, but also all cameras directly connected to it.

You are worried that your hacking effort might get noticed if you interact with the camera control system too much. Write a program that calculates the minimal number of button presses necessary to switch off all cameras.

Input

The first line contains an integer $𝑁$, the number of cameras in the museum.

Each of the following $𝑁 − 1$ lines contains two integers $𝑎$ and $𝑏 (1 \le 𝑎, 𝑏 \le N, 𝑎 \not= 𝑏)$. This means that cameras $𝑎$ and $𝑏$ are directly connected by a wire.

The last line contains $𝑁$ integers. The $𝑖$-th of these integers is $1$ if camera $𝑖$ is turned on at the beginning, and $0$ if camera $𝑖$ is turned off.

Output

Your program should output a single line. This line should consist of an integer, the minimum number of button presses required to turn off all cameras, or the string impossible if it is not possible to turn off all cameras.

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

4

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

impossible

Constraints

It always holds that $3\le N\le 10^5$.

• Subtask 1(5 points). $N\le 20$.
• Subtask 2(15 points). $N\le 40$.
• Subtask 3(10 points). Cameras $𝐴$ and $𝐵$ are directly connected if and only if $|𝐴 − 𝐵| = 1$.
• Subtask 4(40 points). Every camera is directly connected to at most $3$ other cameras.
• Subtask 5(30 points). No further constraints.