作为一名艺术评论家，日复一日地参观博物馆却不被允许触碰展品，这让你感到难以忍受。因此，你决定重操旧业，再次尝试成为一名艺术大盗。然而，在经历了首秀的彻底失败后，你决定这次一定要对监控摄像头做点什么。

相应地，你利用你的 IT 技术侵入了摄像头控制系统。不幸的是，这些摄像头本身是近期装置艺术作品《Xanadu》的一部分。这导致了一种相当奇怪的行为：博物馆内分布着 $N$ 个摄像头（编号为 $1, \dots, N$），其中一些可能因为艺术原因已经处于关闭状态。这 $N$ 个摄像头通过 $N-1$ 条线路连接，使得任意两个摄像头之间都可以直接或间接地连通。摄像头控制系统为每个摄像头提供了一个按钮。然而，按下某个按钮不仅会切换该摄像头的状态，还会同时切换所有与它直接相连的摄像头的状态。

你担心如果与摄像头控制系统的交互过多，你的黑客行为可能会被察觉。请编写一个程序，计算关闭所有摄像头所需的最少按钮按下次数。

输入格式

第一行包含一个整数 $N$，表示博物馆中摄像头的数量。

接下来的 $N-1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le N, a \neq b$)，表示摄像头 $a$ 和 $b$ 之间有一条直接相连的线路。

最后一行包含 $N$ 个整数。其中第 $i$ 个整数为 1 表示摄像头 $i$ 初始时处于开启状态，为 0 表示摄像头 $i$ 初始时处于关闭状态。

输出格式

你的程序应输出一行。该行应包含一个整数，表示关闭所有摄像头所需的最少按钮按下次数；如果无法关闭所有摄像头，则输出字符串 impossible。

数据范围

始终满足 $3 \le N \le 100\,000$。

• 子任务 1（5 分）：$N \le 20$
• 子任务 2（15 分）：$N \le 40$
• 子任务 3（10 分）：摄像头 $A$ 和 $B$ 直接相连当且仅当 $|A - B| = 1$。
• 子任务 4（40 分）：每个摄像头最多与 3 个其他摄像头直接相连。
• 子任务 5（30 分）：无附加限制。

样例

样例输入 1

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

样例输出 1

4

样例输入 2

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

样例输出 2

impossible

说明

下图展示了第一个样例：

关闭所有摄像头的最优按钮按下序列是依次按下摄像头 4、5、3 和 1 的按钮。