Byteasar 和他的朋友们想要结算上次露营旅行的费用。共有 $n$ 名露营者，第 $i$ 名露营者目前的银行账户余额为 $x_i$，在所有费用结算完成后，他们的余额应该为 $y_i$。

Byteotia 的银行转账费用相当昂贵，但有一种变通方法。每个人都可以在银行系统中定义任意数量的“好友”。好友关系是相互的，即如果 A 将 B 定义为好友，那么 A 也是 B 的好友。为了防止反社会行为，没有人可以将自己定义为好友。目前，所有银行都提供一项特殊的优惠：每个人都可以同时向他们的每一位好友免费转账 1 个 bythaler，且此类操作的次数没有限制。

露营者们定义了 $n-1$ 对好友关系，形成了一个网络，使得任意两人之间都可以通过好友链相连，即可以通过仅在好友之间进行常规转账（非优惠的免费转账）在任意两名露营者之间转移资金。现在，露营者们想知道是否仅使用这些免费的特殊转账就能结算他们的露营费用。注意，账户余额允许为负数。

输入格式

第一行包含一个整数 $n$ ($n \ge 2$)，表示露营者的数量。露营者编号为 $1$ 到 $n$。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($0 \le x_i \le W$)，表示露营者当前的账户余额。第三行包含 $n$ 个整数 $y_1, y_2, \dots, y_n$ ($0 \le y_i \le W$)，表示期望的最终账户余额。

接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示露营者 $a_i$ 和 $b_i$ 在银行系统中被指定为好友。

输出格式

第一行输出一个单词：如果可以通过免费特殊转账结算账户，输出 TAK（波兰语中的“是”），否则输出 NIE（波兰语中的“否”）。如果答案为肯定，第二行应包含一个整数：所需的最小特殊转账次数。

样例

样例输入 1

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

样例输出 1

TAK
4

说明

下表展示了一种使用四次特殊转账结算账户的方法。后续行提供了过程中每一步的账户余额。

子任务

测试集包含以下子集。每个子集内可能包含多个测试点。