[R61E]树 - 代码源竞赛平台

时空限制

1S/512M

题目描述

你需要构造一棵包含 $n$ 个节点的有根树，节点编号为 $1 \sim n$。

这棵树必须满足以下条件：

• 对于树上的任意两个节点 $x$ 和 $y$，它们的最近公共祖先的编号等于：将 $x$ 和 $y$ 各自的质因子按从大到小的顺序排列后，这两个质因子序列的最长公共前缀中所有质因子的乘积（如果最长公共前缀为空序列，则乘积规定为 $1$）。

例如，若 $x=12$，$y=18$：

• $x$ 的质因子从大到小排列为 $[3, 2, 2]$
• $y$ 的质因子从大到小排列为 $[3, 3, 2]$ 这两个序列的最长公共前缀为 $[3]$，其乘积为 $3$，因此在这棵树上 $12$ 和 $18$ 的最近公共祖先是节点 $3$。

格式

输入格式

第一行一个正整数 $n$，表示树的节点个数。

输出格式

输出 $n$ 个正整数，第 $i$ 个整数表示节点 $i$ 的父节点编号，如果当前节点是根节点，则输出 $0$。

如果有多棵树满足条件，输出任意一棵即可。

样例

样例输入 #1

6

样例输出 #1

0 1 1 2 1 3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$10$
$2$	$20$	$100$
$3$	$60$	$10^6$

对于 $100\%$ 的数据，$2 \le n \le 10^6$。