← 返回题目列表

AtCoder · agc035_c

C. Skolem 异或树

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

分数: 700 点

问题陈述

给你一个整数 N。判断是否存在一棵树 2N 顶点编号 1 to 2N 满足以下条件,如果答案是肯定的,则显示一棵这样的树。

  • 假设对于每个整数 i 之间 1 和 N (含),顶点 i 和 N+i 有重量 i。然后,对于每个整数 i 之间 1 和 N,Vertex 之间路径上的顶点权重按位异或 i 和 N+i (包括他们自己)是 i.

约束

  • N 是一个整数。
  • 1 \leq N \leq 10^{5}

输入

输入由标准输入按以下格式给出:

N

输出

如果存在满足语句中条件的树,则打印 Yes;否则,打印 No。 然后,如果存在这样的树,则打印 2N-1 随后的此类树的边缘 2N-1 行,格式如下:

a_{1} b_{1}
\vdots
a_{2N-1} b_{2N-1}

这里每对 (a_i, b_i) 表示有一条边连接 Vertex a_i 和 b_i。边缘可以按任何顺序打印。


示例输入 1

3

示例输出 1

Yes
1 2
2 3
3 4
4 5
5 6
  • 示例输出如下图所示:
    d004b05438497d50637b534e89f7a511.png

示例输入 2

1

示例输出 2

No
  • 没有满足条件的树。