题目描述

给定正整数 $n(n \ge 3)$，你需要构造一棵 $n$ 个节点的树，点有点权，使之满足如下要求。

• 对于任一节点，其点权为不超过 $11000$ 的正整数。
• 对于任一不大于 $n$ 的正整数 $k$，都存在树上的一条长度不小于 $1$ 的链，使得该链上所有点权的最大公约数为 $k$，其中链的长度定义为其经过的边数。

在本题的数据范围内答案一定存在，如果有多种构造方案，输出任意一组即可。

输入格式

输入一行一个正整数 $n$。

输出格式

输出共 $n$ 行。

第一行输出 $n$ 个正整数，其中第 $i$ 个数表示你构造的树上节点 $i$ 的点权。

接下来 $n - 1$ 行，每行包含两个正整数 $u$ 和 $v$，表示你构造的树上有一条连接 $u$ 和 $v$ 的边。

输出任意一组构造方案即可。

3

2 6 3
1 2
2 3

4

3 6 8 12
1 2
2 3
3 4

5

10 15 6 8 4
1 2
2 3
3 4
4 5

数据范围与提示

共 $25$ 个测试点，每个测试点 $4$ 分。

对于所有数据，$3 \le n \le 2500$。