← 返回题目列表

Codeforces · 1950/F

F. 0、1、2,树!

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

求满足以下条件的、具有 $$$a+b+c$$$ 顶点的有根树$$$^{\dagger}$$$ 的最小高度:

- $$$a$$$ 顶点恰好有 $$$2$$$ 子节点,
- $$$b$$$ 顶点恰好有 $$$1$$$ 子节点,并且
- $$$c$$$ 顶点恰好有 $$$0$$$ 子节点。

上面的树以顶部顶点为根,每个顶点都标有其子节点的数量。这里$$$a=2$$$,$$$b=1$$$,$$$c=3$$$,高度为$$$2$$$。

$$$^{\dagger}$$$ 有根树是一个没有循环的连通图,有一个称为根的特殊顶点。在有根树中,由边连接的任意两个顶点中,一个顶点是父顶点(距离根较近的顶点),另一个顶点是子顶点。

树中两个顶点之间的距离是它们之间的最短路径中的边数。有根树的高度是从顶点到根的最大距离。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$0 \leq a, b, c \leq 10^5$$$; $$$1 \leq a + b + c$$$)。

所有测试用例的 $$$a + b + c$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果不存在这样的树,则输出$$$-1$$$。否则,输出一个整数——满足语句中条件的树的最小高度。

示例

输入 #1

10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1

输出 #1

2
0
1
1
-1
3
6
-1
-1
3

注意

第一个测试用例如声明中所示。可以证明,你不可能得到小于$$$2$$$的高度。

在第二个测试用例中,您可以形成一棵具有单个顶点且没有边的树。它的高度为 $$$0$$$,这显然是最佳的。

在第三个测试用例中,您可以形成一棵树,其中两个顶点由一条边连接起来。它的高度为$$$1$$$,这显然是最佳的。