#P18463. Distinct Game

Distinct Game

Distinct Game

给定两个数组 a1,a2,…,ana_1,a_2,\ldots,a_n 和 b1,b2,…,bmb_1,b_2,\ldots,b_m,其中 n+m=2kn+m=2k。两个数组中的所有值都在 11 到 kk 之间,且每个值恰好出现两次。一个值的两次出现可以都在同一数组,也可以分别在两个数组。

两名玩家轮流进行操作,由第一名玩家先行动。每次操作,当前玩家从任意一个非空数组的末尾取走一个元素,并将这个元素归自己所有。所有元素都被取走时,游戏结束。

如果第二名玩家取到的所有元素互不相同,则第二名玩家获胜;否则第一名玩家获胜。双方都采用最优策略,判断哪名玩家能够保证获胜。

输入格式

第一行包含整数 tt(1≤t≤1051\le t\le10^5),表示测试用例数。

每个测试用例第一行包含整数 n,mn,m(1≤n,m≤5⋅1051\le n,m\le5\cdot10^5),表示两个数组的长度。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行包含 mm 个整数 b1,b2,…,bmb_1,b_2,\ldots,b_m。

保证 n+mn+m 为偶数,所有元素都在 11 到 k=(n+m)/2k=(n+m)/2 之间,且每个值恰好在两个数组中合计出现两次。

保证全部测试用例的 n+mn+m 之和不超过 10610^6。

输出格式

对于每个测试用例输出一行:如果第一名玩家有必胜策略,输出 1;否则输出 2。

完整原样例输入

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

完整原样例输出

2
1
2
2