← 返回题目列表

Codeforces · 1270/G

G. 零和子集

中文机器翻译题面 查看原题

给定 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$,这样对于每个 $$$1\le i \le n$$$ 都包含 $$$i-n\le a_i\le i-1$$$。

找到这些整数的一些非空子集,其总和等于 $$$0$$$。可以证明在给定的约束下存在这样的子集。如果存在多个可能的零和子集,则可以找到其中任何一个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^6$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$i-n \le a_i \le i-1$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出两行。

在第一行中,输出 $$$s$$$ ($$$1\le s \le n$$$) — 子集中的元素数量。

在第二行中,输出 $$$s$$$ 整数 $$$i_1, i_2, \dots, i_s$$$ ($$$1\le i_k \le n$$$)。所有整数必须成对不同,并且 $$$a_{i_1} + a_{i_2} + \dots + a_{i_s}$$$ 必须等于 $$$0$$$。如果存在多个可能的零和子集,则可以找到其中任何一个。

示例

输入 #1

2
5
0 1 2 3 4
4
-3 1 1 1

输出 #1

1
1 
4
1 4 3 2

注意

在第一个示例中,我们得到的总和是 $$$a_1 = 0$$$。

在第二个示例中,我们得到的总和为 $$$a_1 + a_4 + a_3 + a_2 = 0$$$。