※ 下发文件链接 ，本题英文名为 $\texttt{end}$ ，不需要 freopen ，不开启 O2 优化和 C++11 。
※ 跳过剧情的同学请从分割线开始看哦~
从学习「磁力术」到掌握「屏障术」，从战术演练到与黑暗势力实战，ω 已了然于胸——这些都只不过是人生中的云烟。当她在最信任的人面前持起法杖，ω 发现，坚毅的勇气给予了她真正的成长。
「老师，你彻底变了，对不起……」ω 强忍住泪水，竭尽全力使出了曾苦苦钻研的光明法术。只见透亮的光芒瞬间拨开了压抑的黑雾，击破了 Ω 的重重黑暗法术。紧接着是一声爆炸的巨响，Ω 被一股强大的能量摁倒在地，有气无力地挣扎着……
「不得不说……你……是我见过最有天赋的……魔法少女……」Ω 奄奄一息道，「不……过……『魔法少女』……这个词……恐怕……只是个笑话吧……」
留下让人不知所云的话语，Ω 的身体逐渐变得透明，消散在了空气之中。
「就这样结束了吗？」ω 茫然地愣了许久。或许她完成了 Ω 赐予她的最后一个试炼，但 ω 却始终高兴不起来，此时她的脑袋里只存有一片空白……
若干年后。
主持魔法学院重建工作的 ω 坐在围墙上，与一旁的少女交谈。
「老师老师，你知道咱们学院是怎么传递信息的吗？」
「当然知道啊！」ω 笑着摸了摸少女的头说道，「魔法学院有 $n$ 处地点，它们依次编号为 $1$ 到 $n$ 。我们搭设了 $n - 1$ 条线路，第 $i$ 条线路连接 $u_i$ 号地点和 $v_i$ 号地点。当然，任意两处地点间都存在一条由线路构成的路径。」
少女调皮地歪了下脑袋。「但是老师，为什么我在 $1$ 号地点，经常收不到 $n$ 号地点的信息呢？」
「因为怕狡猾的敌人窃听我们啊。」ω 回答道，「学院内部只使用 $m$ 个频道，每处地点分别会选择性地屏蔽一些频道。两处地点能够直接通信，当且仅当它们被一条线路所连接，且存在两处地点都没有屏蔽的频道。为了测评通讯质量，我们定义『通讯值』为最多能把 $n$ 处地点分成多少非空组，满足不同组内的地点无法直接通信。」
「这样一成不变的话，行动不是迟早会暴露在敌人面前吗？」
「是啊。所以我们打算轮流执行 $q$ 次修改，第 $i$ 次修改会改变 $x_i$ 号地点的频道屏蔽状态。现在我来考考你，在修改之前以及每次修改后，你能分别求出通讯值是多少吗？」
少女微微一笑，仿佛心中已有了答案。
第一行，包含两个正整数 $n,\,m$ ，分别为魔法学院地点和频道的数量。
接下来 $n - 1$ 行，其中第 $i$ 行包含两个正整数 $u_i,\,v_i$ ，表示第 $i$ 条线路连接 $u_i$ 号地点和 $v_i$ 号地点。
再接下来 $n$ 行，其中第 $i$ 行包含一个长度为 $m$ 的 01 串 $s_i$ ，01 串的第 $j$ 位为 0 表示 $i$ 号地点屏蔽了频道 $j$ ，1 则表示未屏蔽。
第 $n + n + 1$ 行，包含一个整数 $q$ ，为修改次数。
接下来 $q$ 行，其中第 $i$ 行包含一个正整数 $x_i$ 和一个长度为 $m$ 的 01 串 $t_i$ ，01 串的第 $j$ 位为 0 表示将 $x_i$ 号地点改为屏蔽频道 $j$ ，1 则表示取消屏蔽。
共 $q + 1$ 行，其中第一行输出一个整数表示修改前的通讯值，第 $i + 1$ 行（$1 \le i \le q$）输出一个整数表示第 $i$ 次修改后的通讯值。
Comet OJ3 2
1 2
2 3
11
01
10
026 4
1 2
2 3
2 4
1 5
5 6
1111
0011
1000
0100
0010
0001
3
2 0110
1 1001
5 11114
3
5
3见下发文件中 end3.in见下发文件中 end3.ans
对于具有 特殊性质 $1$ 的数据，有 $u_1 = u_2 = u_3 = \cdots = u_{n-1} = 1$ 。
对于具有 特殊性质 $2$ 的数据，有 $x_1 = x_2 = x_3 = \cdots = x_q = 1$ 。
对于具有 特殊性质 $3$ 的数据，被修改地点的 $m\ (m > 1)$ 个频道中最多只有一个频道的屏蔽状态与修改前不同。
对于所有的数据，保证 $2 \le n \le 10^5,\ 1 \le m \le 20,\ 0 \le q \le 10^5,\ 1 \le u_i,\,v_i,\,x_i \le n,\ |s_i| = |t_i| = m$ 。