← 返回题目列表

Codeforces · 2112/E

E. 树着色

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

考虑一棵有根无向树。每个顶点可以着色为蓝色、绿色或黄色。有一种着色叫做 美丽 如果满足以下条件:

  • 树的根是绿色的;
  • 如果你考虑 所有蓝色和绿色顶点,它们无需经过任何 黄色 顶点;
  • 如果你考虑 所有黄色和绿色顶点,它们无需经过任何 蓝色 顶点;

给你一个整数 $$$m$$$。您的任务是计算树中的最小顶点数 正是 $$$m$$$ 美丽 着色。

输入

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

每个测试用例的唯一行包含一个整数 $$$m$$$ ($$$1 \le m \le 5 \cdot 10^5$$$)。

输出

对于每个测试用例,打印一个整数 - 树中顶点的最小数量 正是 $$$m$$$ 美丽 着色。如果这样的树不存在,则打印$$$-1$$$。

示例

输入
复制

5
1
3
5
7
9

输出
复制

1
2
3
4
3

注意

在下面的注释中,让 $$$g$$$ 描述绿色,$$$b$$$ 描述蓝色,$$$y$$$ 描述黄色。

在第一个示例中,考虑一棵只有 $$$1$$$ 顶点的简单树。这棵树有 $$$1$$$ 漂亮的颜色:根是绿色的。

在第二个示例中,考虑一棵具有 $$$2$$$ 顶点且根位于 $$$1$$$-st 顶点的简单树。总共有 $$$3$$$ 漂亮的颜色:$$$[g, g]$$$、$$$[g, b]$$$ 和 $$$[g, y]$$$。

在第三个示例中,考虑一棵具有 $$$3$$$ 顶点、根位于 $$$1$$$-st 顶点的竹树。恰好有 $$$5$$$ 漂亮的颜色:$$$[g, g, g]$$$、$$$[g, g, b]$$$、$$$[g, g, y]$$$、$$$[g, b, b]$$$ 和 $$$[g, y, y]$$$。

在第五个示例中,考虑一棵具有 $$$3$$$ 顶点的树,根位于 $$$1$$$-st 顶点,其他 $$$2$$$ 顶点连接到它。正好有$$$9$$$漂亮的颜色:$$$[g, g, g]$$$, $$$[g, g, b]$$$, $$$[g, g, y]$$$, $$$[g, b, g]$$$, $$$[g, b, b]$$$, $$$[g, b, y]$$$, $$$[g, y, g]$$$, $$$[g, y, b]$$$ 和$$$[g, y, y]$$$。