← 返回题目列表

Codeforces · 1038/B

B. 非互质分区

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

找出是否可以将前 $$$n$$$ 正整数划分为两个非空不相交集合 $$$S_1$$$ 和 $$$S_2$$$,这样:

$$$\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1$$$

这里 $$$\mathrm{sum}(S)$$$ 表示集合 $$$S$$$ 中所有元素的总和,$$$\mathrm{gcd}$$$ 表示最大公约数。

从 $$$1$$$ 到 $$$n$$$ 的每个整数都应该恰好出现在 $$$S_1$$$ 或 $$$S_2$$$ 之一中。

输入

输入的唯一行包含单个整数 $$$n$$$ ($$$1 \le n \le 45\,000$$$)

输出

如果这样的分区不存在,则打印“No”(为了清楚起见,加引号)。

否则,打印“Yes”(为清楚起见,加引号),后跟两行,分别描述 $$$S_1$$$ 和 $$$S_2$$$。

每个集合描述都以集合大小开始,后面是按任意顺序排列的集合元素。每组必须非空。

如果有多个可能的分区 - 打印其中任何一个。

示例

输入 #1

1

输出 #1

No

输入 #2

3

输出 #2

Yes
1 2
2 1 3

注意

在第一个示例中,无法将单个数字划分为两个非空集合,因此答案为“否”。

在第二个示例中,集合的总和分别为 $$$2$$$ 和 $$$4$$$。 $$$\mathrm{gcd}(2, 4) = 2 > 1$$$,因此这是可能的答案之一。