题目描述
经过了长时间的努力,团长终于让所有的团员都成功脱团了,而且有的双方都是原死死团成员。因此团长想要知道有多少对情侣曾经都是死死团成员。在死死团中,成员们的关系可以表示成一颗有向树,男生和女生各一颗。如果男生关系树中某颗子树和女生关系树中的某颗子树刚好形态相同,我们认为它们是公共子树。死死团的内部情侣,正好对应着节点数最多的公共子树,即该公共子树的节点数等于内部情侣数。现在对于给定的男生关系树和女生关系树,请你计算出最大公共子树的节点数。
对于40%的数据:1 ≤ N,M ≤ 10
对于100%的数据:1 ≤ T ≤ 10,1 ≤ N,M ≤ 50
输入格式
第1行:1个正整数T,表示测试组数
接下来T组测试数据,每组如下格式:
第1行:两个正整数N和M,表示男生人数N,女生人数M
第2..N行:描述第一棵树,每行2个正整数a和b,表示a的父亲是b
第N+1..N+M-1行:描述第二棵树,同上
输出格式
第1..T行:每行1个整数,表示最大公共子树的节点数
样例输入
样例输出