#P9652. Skolem XOR Tree

    ID: 6269 传统题 2000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200提高图构造分块构造异或抵消lowbit

Skolem XOR Tree

题目描述

给定一个正整数 NN。

试判断,是否存在这样一棵节点数为 2N2N 的树,满足:

  • ∀i∈[1,n]\forall i\in[1,n],第 ii 号节点和第 i+ni+n 号节点的权值均为 ii。
  • 第 ii 号节点到第 i+Ni+N 号节点路径上的点的点权异或和恰为 ii。

输入格式

仅一行一个整数 NN。

输出格式

若不存在这样的树,请输出一行 No。

否则先输出一行 Yes,然后再输出 2N−12N-1 行,每行两个正整数 u,vu,v 描述树上的一条连接 u,vu,v 的边。

样例

3
Yes
1 2
2 3
3 4
4 5
5 6
1
No

数据范围

对于全部数据,1≤N≤1051\le N\le 10^5。