← 返回题目列表

Codeforces · 1763/E

E. 节点对

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

我们将有向图中的一对有序节点 $$$(u, v)$$$ 称为单向,如果 $$$u \neq v$$$ 存在从 $$$u$$$ 到 $$$v$$$ 的路径,并且不存在从 $$$v$$$ 到 $$$u$$$ 的路径。

如果有向图恰好包含 $$$p$$$ 有序节点对 $$$(u, v)$$$ 使得 $$$u < v$$$ 且 $$$u$$$ 和 $$$v$$$ 彼此可达,则称有向图 $$$p$$$ 可达。求创建 $$$p$$$ 可达有向图所需的最小节点数。

此外,在所有此类具有最小节点数的$$$p$$$可达有向图中,令$$$G$$$表示最大化单向节点对的数量的图。找到这个号码。

输入

第一行也是唯一一行包含一个整数 $$$p$$$ ($$$0 \le p \le 2 \cdot 10^5$$$) — 有序节点对的数量。

输出

打印包含两个整数的单行 - 创建 $$$p$$$ 可到达有向图所需的最小节点数,以及所有此类具有最小节点数的 $$$p$$$ 可到达有向图中单向节点对的最大数量。

示例

输入 #1

3

输出 #1

3 0

输入 #2

4

输出 #2

5 6

输入 #3

0

输出 #3

0 0

注意

在第一个测试用例中,创建$$$3$$$可达有向图所需的最小节点数为$$$3$$$。在所有具有$$$3$$$节点的$$$3$$$可达有向图中,下面的图$$$G$$$是单向节点对数量最多的图之一,即$$$0$$$。