题目描述

有一个 $n$ 个点的完全图，点的编号为 $1,2,\dots,n$，$i,j$ 之间有长度为为 $\gcd(i,j)$ 的边。求该图最短哈密顿回路的长度，并给出一组方案。

输入格式

输入一行一个正整数 $n\ (1\le n\le 400)$。

输出格式

输出一个 $1\sim n$ 的排列，顺次为最短哈密顿回路经过的点。