← 返回题目列表

AtCoder · tenka1_2018_d

D. 穿越

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

分数: 500 点

问题陈述

给你一个整数 N。判断是否存在子集的元组 \{1,2,...N\}, (S_1,S_2,...,S_k),满足以下条件:

  • 每个整数 1,2,...,N 正好包含在其中两个集合中 S_1,S_2,...,S_k.
  • 任意两组 S_1,S_2,...,S_k 恰好有一个共同点。

如果存在这样的元组,则构造一个这样的元组。

约束

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

输入

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

N

输出

如果一个元组的子集 \{1,2,...N\} 满足条件的不存在,打印 No。 如果存在这样的元组,则打印 首先 Yes ,然后按以下格式打印此类子集:

k
|S_1| S_{1,1} S_{1,2} ... S_{1,|S_1|}
:
|S_k| S_{k,1} S_{k,2} ... S_{k,|S_k|}

其中 S_i={S_{i,1},S_{i,2},...,S_{i,|S_i|}}.

如果有多个这样的元组,则其中任何一个都将被接受。


示例输入 1

3

示例输出 1

Yes
3
2 1 2
2 3 1
2 2 3

可以看出 (S_1,S_2,S_3)=(\{1,2\},\{3,1\},\{2,3\}) 满足条件。


示例输入 2

4

示例输出 2

No