[SDOI2013] 刺客信条

题目描述

故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师,他不仅是个身手敏捷的武林高手,飞檐走壁擅长各种暗杀术。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。 曾经有一次,为了寻找Altair 留下的线索和装备,Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室,且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记,他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室,Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印,他需要通过改变某些刺客标记的启动情况,使得所有刺客标记与封印密码“看起来一样”。 在这里,“看起来一样”的定义是:存在一种“标记”密室与“密码”密室之间一一对应的关系,使得密室间的连接情况和启动情况相同(提示中有更详细解释)。幸运的是,在Ezio 来到刺客墓穴之前,在Da Vinci 的帮助下,Ezio 已经得知了打开储藏室所需要的密码。 而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

输入输出格式

输入格式


第一行给出一个整数n, 表示密室的个数, 第二行至第 n 行, 每行绐出两个整数 a 和 b, 表示第 a 个密室和第 b 个密室之间存在一条通道. 第 n+1行1 绐出 n 个整数1 分别表示当时每个密室的启动情况 {0表示关闭, 1表示启动). 第 n+2 行7 给出 n 个整数, 分别表示密码中每个密室的启动情况.

输出格式


输出只有一行,即输出最少改动标记次数

输入输出样例

输入样例 #1

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

输出样例 #1

1

说明

密室的编号是可以变的!将第三个密室关闭后,在当前标记和密码之间,存在1->4,2->3,3->2,4->1 的对应关系,重新编号后连接情况没有改变,且标记与密码对应。对于更一般的情况,存在一个1 到n 的置换P,使得对于任意密室之间的道路u-v,都一定有密码密室中的道路P(u)-P(v);如果不存在密室之间的道路u-v,则一定没有密码密室中的道路P(u)-P(v)。 对于100%的数据,n<=700,且每个密室至多与11个密室相通