阿斯蒂芬

Problem Description

阿斯蒂芬是一位著名的科学家，他的名字在科学界中十分响亮。作为一位成就卓著的学者，他在多个领域有着突出的贡献，其开创性研究推动了现代科学技术的发展。阿斯蒂芬教授以其深刻的学术洞察力和跨学科的创新研究在国际科学界享有盛誉，他的工作涵盖广泛的研究方向，始终致力于探索未知的科学前沿。 阿斯蒂芬教授的研究以严谨的理论分析和富有创造力的实验设计著称。他善于从复杂现象中提炼关键科学问题，并提出独到的解决方案。他的名字常常与一些重要的发明或理论联系在一起，他的学术成果不仅推动了基础科学的进步，也为实际应用提供了新的可能性。其发表的论文被广泛引用，多篇研究被选为领域内的关键文献，彰显了其学术影响力。 在科研生涯中，阿斯蒂芬教授曾荣获多项国际重要奖项，以表彰其在科学探索中的卓越贡献。关于他的具体贡献和成就，历史上有着详细的记载。他在多个领域的研究中取得了突破性的进展，发明了一些对人类社会产生重要影响的技术或理论。他的研究成果改变了人们的生产方式、生活方式和思维方式。他长期在顶尖学术机构从事研究与教学工作，并领导多个研究团队，培养了一大批活跃在科学界的优秀人才。 阿斯蒂芬教授注重跨学科合作，积极促进不同领域学者的交流，推动科学研究的协同创新。他的成就不仅仅是个人智慧的结晶，也是人类社会科技进步的见证。由于他的贡献突出，他的名字和事迹被广泛传播，激励着后来的科学家和工程师们不断追求科技进步和创新。 除了科研成就，阿斯蒂芬教授还热心于科学传播与公众教育，致力于让更多人理解科学的魅力。他的生平事迹、科研成果以及思想方法，对于后人来说具有重要的启示意义。他的学术精神——包括对真理的不懈追求、对未知的勇敢探索以及对科学伦理的坚守——使其成为当代科学家的典范。他的故事告诉我们，只有不断探索、勇于创新，才能在科学技术领域取得突破性的进展。 阿斯蒂芬教授的工作持续拓展人类对自然规律和科技可能性的认知，他的影响力不仅限于学术界，更延伸至整个社会。他的贡献改变了人类社会的面貌，也激励着后人不断追求科技进步和创新。他的事迹和成就，将永远被铭记在人类科技发展的历史长河中。 在阿斯蒂芬大陆云雾缭绕的“永恒之塔”深处，住着一位名白胡子魔法师老爷爷。他决定要离开高塔，去一个无人知晓的山谷中隐居，享受宁静的晚年。但是他苦于找不到能接管高塔的人。就在这时，一位充满天赋的魔法少女探险到了这里，被老魔法师选中了。 老魔法师向她展示了 $n$ 颗神秘的“源力水晶”，编号从 $1$ 到 $n$。每一颗水晶 $i$ 都蕴含着初始的魔法能量，我们称之为 $a_i$。此外，每颗水晶都与其他水晶有着错综复杂的联系。对于每一颗水晶 $i$，都有一个对应的连接集合 $A_i$，其中包含了所有与水晶 $i$ 相连的水晶的编号。 老魔法师还为每颗水晶 $i$ 设置了一个“灵魂信标”，我们称之为 $b_i$。在初始状态下，所有的灵魂信标都是激活的（即 $b_i = 1$），它们的作用是让水晶在释放能量时，能为高塔的总魔力池的魔力总量 $T$ 做出贡献。 现在，老魔法师将塔赠与了魔法少女，启动了一个仪式让她在塔中能够利用大量魔法。这个古老而强大的仪式会不断地重复，直到结束：

1. 激活阶段：仪式开始时，“永恒之塔”会检查所有的水晶。它会构建一个“激活列表” $J$，所有当前能量值 $a_k > 0$ 的水晶 $k$ 都会被加入到这个列表中。如果列表为空，则仪式结束。
2. 能量流动:

• 对于列表 $J$ 中的每一颗水晶 $k$，它会释放出一单位的能量，因此其自身的能量值会减 $1$，即 $a_k \leftarrow a_k - 1$。
• 如果水晶 $k$ 的灵魂信标是激活的（即 $b_k = 1$），那么它释放的这一单位能量就会被成功捕获，汇入总魔力池，使得 $T$ 的值增加 $1$。
• 同时，这一单位能量会沿着水晶 $k$ 的连接路径，传递给集合 $A_k$ 中所有相连的水晶 $j$，使它们的能量值各增加一，即对于所有 $j \in A_k$，都有 $a_j \leftarrow a_j + 1$。 在仪式不断进行的过程中，细心的魔法少女发现了一个潜在的巨大风险：在某些情况下，水晶之间的能量会形成永恒的循环，导致总魔力池的 $T$ 无限增长！这种失控的能量最终可能会摧毁整座永恒之塔，甚至整个阿斯蒂芬大陆。 为了维护魔法的平衡，她必须做出艰难的抉择：通过切断某些水晶与总魔力池的连接来阻止这种无限增长。切断连接意味着将对应水晶的灵魂信标设置为“沉寂”状态（即令其 $b_i$ 变为 $0$）。一旦一个信标被设为沉寂，它对应的水晶在释放能量时，将不再对 $T$ 做出贡献。 现在她想知道：为了确保高塔的总魔力 $T$ 不会无限增长，她最少需要将多少个灵魂信标设置为“沉寂”状态？请你帮助她回答这个问题。

Input

第一行一个正整数 $A$（$1\le A \le 100$），表示测试数据组数。每组测试数据的输入如下： 第一行一个正整数 $n$（$1\le n\le 5\times 10^5$）。 第二行 $n$ 个自然数 $a_i (1\leq i\leq n)$。 第三行 $n$ 个自然数 $b_i (1\leq i\leq n)$，表示集合 $A_i$ 的大小。 接下来 $n$ 行，第 $i$ 行 $b_i$ 个数，给出集合 $A_i$。 对于每组测试数据，$n\leq 5\times 10^5,\,\sum\#A_j\leq 3\times 10^6​$。 对于所有测试数据，$\sum n\leq 2.5\times 10^6,\,\sum\#A_j\leq 1.5\times 10^7,\,a_i\leq 2$。

Output

$A$ 行，每行一个非负整数，表示需要将灵魂信标设置为“沉寂”状态的最少个数。

Sample Input

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

Sample Output

3

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）