#P1733. Collective Mindsets (hard)

Collective Mindsets (hard)

题目描述

一共有 nn 个僵尸,每个僵尸头上有一个 1n1 \sim n 之间的数字(可重复!),每个僵尸只能看到其他 n1n - 1 个僵尸头顶的数字,当然,他们也知道自己的编号。 要求提供一种策略,使所有僵尸只利用自己知道的信息同时猜自己头顶的数字,保证至少有一个僵尸猜对。

输入格式

第一行,一个正整数 TT,表示数据组数。

接下来对于每组数据,第一行包含两个正整数 nnrr,表示僵尸总数与当前僵尸的编号,下一行包括 n1n-1 个正整数,表示当前僵尸看到的所有其他僵尸头顶的编号是多少(按僵尸编号升序排列)。

输出格式

对于每组数据输出一行一个整数,表示该僵尸的猜测。

输入数据 1

4
2 1
1
2 2
1
2 1
2
2 2
2

输出数据 1

1
2
2
1

输出数据 1

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

说明 / 提示

1T500001 \le T \le 500002n62 \le n \le 61rn1 \le r \le n