题目描述

请在 $N$ 维空间中，按照以下条件，配置 $N$ 个点 $p_1,\ p_2,\ \dots,\ p_N$。

条件 1 点的坐标必须由 $0$ 到 $10^8$ 之间的整数构成。

条件 2 对于输入给定的 $(A\_1,\ B\_1),\ (A\_2,\ B\_2),\ \dots,\ (A\_{N(N-1)/2},\ B\_{N(N-1)/2})$，需要满足 $d(p\_{A\_1},\ p\_{B\_1}) < d(p\_{A\_2},\ p\_{B\_2}) < \dots < d(p\_{A\_{N(N-1)/2}},\ p\_{B\_{N(N-1)/2}})$。其中 $d(x, y)$ 表示点 $x, y$ 之间的欧几里得距离。

在本题的约束下，保证一定存在解。如果有多组解，只需输出其中一组即可。

欧几里得距离指的是 $n$ 维空间中两点 $x, y$ 的距离，设 $x$ 的坐标为 $(x_1, x_2, \dots, x_n)$，$y$ 的坐标为 $(y_1, y_2, \dots, y_n)$，则距离为 $\sqrt{(x\_1-y\_1)^2 + (x\_2-y\_2)^2 + \dots + (x\_n-y\_n)^2}$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_{N(N-1)/2}$ $B_{N(N-1)/2}$

输出格式

设点 $p_i$ $(1 \leq i \leq N)$ 的坐标为 $(p_{i, 1}, p_{i, 2}, \dots, p_{i, N})$，请按以下格式输出：

$p_{1, 1}$ $p_{1, 2}$ $\cdots$ $p_{1, N}$ $p_{2, 1}$ $p_{2, 2}$ $\cdots$ $p_{2, N}$ $\cdots$ $p_{N, 1}$ $p_{N, 2}$ $\cdots$ $p_{N, N}$

样例 1

输入

4
1 2
1 3
2 4
3 4
1 4
2 3

输出

3 2 0 0
9 1 0 0
1 8 0 0
9 8 0 0

说明/提示

约束

• $3 \leq N \leq 20$
• $1 \leq A\_i < B\_i \leq N\ (1 \leq i \leq \frac{N(N-1)}{2})$
• $(A\_1, B\_1), (A\_2, B\_2), \dots, (A\_{N(N-1)/2}, B\_{N(N-1)/2})$ 均互不相同

样例解释 1

在本输出样例中，坐标的第 $3$、第 $4$ 个分量均为 $0$，因此可以用如下的二维图表示。$d(p_1, p_2) = \sqrt{37}$，$d(p_1, p_3) = \sqrt{40}$，$d(p_2, p_4) = \sqrt{49}$，$d(p_3, p_4) = \sqrt{64}$，$d(p_1, p_4) = \sqrt{72}$，$d(p_2, p_3) = \sqrt{113}$，顺序均正确。

由 ChatGPT 4.1 翻译