#P18226. Growing Tree
Growing Tree
Growing Tree
Little Q 种下了一棵树。最初,树上只有编号为 的根节点,它同时也是叶子。
每天上午,每个叶子节点 都会长出两条新的枝干:
- 一条连接节点 与节点 ,长度为 ;
- 另一条连接节点 与节点 ,长度为 。
之后, 不再是叶子,节点 和 成为新的叶子。树会生长 天,最终形成一棵有 个节点、 个叶子的满二叉树。
在这 天中,每天下午,Little Q 可以选择一条已经长出来的枝干进行修剪,将它的长度改成任意正整数,也可以不修剪。新长度可以小于或大于原长度。
他希望树完全长成后,从根到每个叶子的简单路径上的枝干长度之和两两不同。
求最少需要修剪多少条枝干;如果无法做到,输出 。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例:
- 第一行包含一个整数 ,表示树生长的天数。
- 第二行包含 个整数 ,其中 表示连接节点 与节点 的枝干的原始长度。
数据范围:
$$1\le T\le1000,\qquad 1\le n\le10,\qquad 1\le a_u\le10^8.$$保证整个输入中 的测试用例不超过 个。没有另加所有节点数之和的限制。
原始长度的上界不限制修剪后的新长度;修剪后的长度只需是正整数。
输出格式
对于每个测试用例输出一行:若可以满足要求,输出最少需要修剪的枝干数;否则输出 。
样例
3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1
1
2
-1
样例说明
第一个测试用例中,原来的四条根到叶子的路径长度依次为 。在第一天下午,将枝干 的长度从 改为 ,最终四条长度变成 ,因此只需修剪一条。
第二个测试用例原来的四条长度为 。第一天下午将枝干 的长度改为 ,第二天下午再将枝干 的长度改为 ,四条长度变成 ,可以用两次修剪完成。
第三个测试用例中,两个叶子兄弟对的路径长度分别相同。要区分每一对兄弟,都必须修改其中一条在第二天上午才长出的末端枝干;但第二天下午只能修改一条,故无解。