QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[0]
Statistics

小 T 有一个 n+1 层的满二叉树 T。具体来说,这棵树以 1 为根,共有 2n+11 个结点。对于每个点 x (1x<2n),它的左儿子和右儿子分别为 2x2x+1

有一天,树 T 上每两个相邻的叶子 yy+1 (2ny2n+12) 之间都连了一条边。小 T 对它非常失望,因为它不再是一棵真正的树了。小 T 想到他刚刚学过图论中的缩点,于是他决定应用自己的知识来让它重新变成一棵树。

具体来说,小 T 首先需要决定他所用的颜色数 m,接着他要给每个点 i 染上一种颜色 ci (1cim)。之后建立一张 m 个点的新图 GG 中两点 i,j (ij) 有边当且仅当 T 中存在两个相连的点 u,v 满足 cu=i, cv=j。小 T 要求图 G 必须是一棵树。

为了更加美观,小 T 希望每种颜色至少有 1 个点使用,且至多有 k 个点使用。你能否帮助他构造出想要的方案呢?

输入格式

一行两个数 n,k,分别表示满二叉树层数和每种颜色的数量限制。

输出格式

第一行一个数 m 表示使用的颜色数。

第二行 2n+11 个数,其中第 i 个数表示 i 号点染成的颜色 ci

样例输入 1

1 12

样例输出 1

2
2 2 1

样例输入 2

2 12

样例输出 2

3
2 3 2 1 3 2 3

样例解释

样例 1 中图 G2 个点,有 1 条边 (1,2),边 (1,2) 对应 T 的边 (1,3),(2,3)

样例 2 中图 G3 个点,有 2 条边 (1,3),(3,2),边 (1,3) 对应 T 的边 (4,2),(4,5),边 (3,2) 对应 T 的边 (2,1),(5,6),(3,7),(6,7)

数据范围

对于所有数据,1n2012k1.1×106

子任务 111 分):n4k=12

子任务 28 分):k=1.1×106

子任务 315 分):k=6×105

子任务 416 分):k=5000

子任务 515 分):k=200

子任务 635 分):k=12