#P18463. Distinct Game
Distinct Game
Distinct Game
给定两个数组 和 ,其中 。两个数组中的所有值都在 到 之间,且每个值恰好出现两次。一个值的两次出现可以都在同一数组,也可以分别在两个数组。
两名玩家轮流进行操作,由第一名玩家先行动。每次操作,当前玩家从任意一个非空数组的末尾取走一个元素,并将这个元素归自己所有。所有元素都被取走时,游戏结束。
如果第二名玩家取到的所有元素互不相同,则第二名玩家获胜;否则第一名玩家获胜。双方都采用最优策略,判断哪名玩家能够保证获胜。
输入格式
第一行包含整数 (),表示测试用例数。
每个测试用例第一行包含整数 (),表示两个数组的长度。
第二行包含 个整数 。
第三行包含 个整数 。
保证 为偶数,所有元素都在 到 之间,且每个值恰好在两个数组中合计出现两次。
保证全部测试用例的 之和不超过 。
输出格式
对于每个测试用例输出一行:如果第一名玩家有必胜策略,输出 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