Problem 2997 --AND Minimum Spanning Tree

2997: AND Minimum Spanning Tree

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

You are given a complete graph with N vertices, numbered from 1 to N. 
The weight of the edge between vertex x and vertex y (1<=x, y<=N, x!=y) is simply the bitwise AND of x and y. Now you are to find minimum spanning tree of this graph.
Input

Input

The first line of the input contains an integer T (1<= T <=10), the number of test cases. Then T test cases follow. Each test case consists of one line containing an integer N (2<=N<=200000).

Output

For each test case, you must output exactly 2 lines. You must print the weight of the minimum spanning tree in the 1st line. In the 2nd line, you must print N-1 space-separated integers f2, f3, … , fN, implying there is an edge between i and fi in your tree(2<=i<=N). If there are multiple solutions you must output the lexicographically smallest one. A tree T1 is lexicographically smaller than tree T2, if and only if the sequence f obtained by T1 is lexicographically smaller than the sequence obtained by T2.

Sample Input复制

2
3
2

Sample Output复制

1
1 1
0
1

提示

In the 1st test case, w(1, 2) = w(2, 1) = 0, w(1, 3) = w(3, 1) = 1, w(2, 3) = w(3, 2) = 2. There is only one minimum spanning tree in this graph, i.e. {(1, 2), (1, 3)}.
For the 2nd test case, there is also unique minimum spanning tree.

推荐代码 查看2997 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$45 $ms] llmxby 470050 2019-09-19 11:45:13
内存最少[$2800 $KB] llmxby 470050 2019-09-19 11:45:13
第一AC llmxby 470050 2019-09-19 11:45:13
第一挑战 llmxby 470050 2019-09-19 11:45:13

赛题来源/所属竞赛 2019 Multi-University Training Contest 4 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1407 2019CCPC模拟赛（秦皇岛站 安财贸9.19） 2019-09-19 09:00:00 请登录