The solution

Let’s dive straight into the solution.

Suppose \((p_i, p_j)\) is the \(r_{i, j}\)-th farthest pair of points (meaning \(r_{A_i, B_i} = \frac{N(N-1)}{2} - i + 1\)). Then, the following arrangement of points satisfies the conditions:

\[ \begin{aligned} p_1 & = (L, r_{1, 2}, \dots, r_{1, N}) \\ p_2 & = (0, L, \dots, r_{2, N}) \\ & \vdots \\ p_N & = (0, 0, \dots, L) \end{aligned} \]

Here, \(L\) is a sufficiently large constant. Under the constraints of this problem, \(L = 10^8\) is sufficient.

---

How to come up with the solution

Hearing the solution, you might think it’s a stroke of genius, but it’s possible to arrive at this solution through a natural line of thought.

Below, I will describe the steps of reasoning that lead to the solution.

1. Start with the case where “all are equal”

In competitive programming, even if it seems difficult to start, you can often find clues in the solutions to limited or simplified versions of the problem.

In this problem, instead of directly thinking about an arrangement of points that satisfies \(d(p_{A_1}, p_{B_1}) < \dots < d(p_{A_{N(N-1)/2}}, p_{B_{N(N-1)/2}})\), let’s first consider the case where “<” is replaced with “=”; that is, finding an arrangement of \(N\) points where the distance between any two points is equal.

For \(N = 3\), placing the points in an equilateral triangle satisfies the conditions, so \(p_1 = (1, 0, 0), p_2 = (0, 1, 0), p_3 = (0, 0, 1)\) works. The same arrangement can be applied for a general \(N\).

\[ \begin{aligned} p_1 & = (1, 0, \dots, 0) \\ p_2 & = (0, 1, \dots, 0) \\ & \vdots \\ p_N & = (0, 0, \dots, 1) \end{aligned} \]

Here, the distance between any two points is \(\sqrt{2}\).

2. Fine-tune to get the distances in the correct order

Let’s adjust the “all distances are the same” solution to get the distances in the correct order. However, for now, let’s forget about the constraint that coordinates must be integers. The following figure illustrates adjusting the equilateral triangle for \(N = 3\) to create a solution where \(d(p_2, p_3) < d(p_1, p_3) < d(p_1, p_2)\).

Let’s think about how to adjust in terms of formulas. If we denote the amount of adjustment by \(\epsilon_{i, j}\) (a very small value), the coordinates of the points are as follows:

\[ \begin{aligned} p_1 & = (1+\epsilon_{1,1}, \epsilon_{1,2}, \dots, \epsilon_{1,N}) \\ p_2 & = (\epsilon_{2,1}, 1+\epsilon_{2,2}, \dots, \epsilon_{2,N}) \\ & \vdots \\ p_N & = (\epsilon_{N,1}, \epsilon_{N,2}, \dots, 1+\epsilon_{N,N}) \end{aligned} \]

In this case, the distance between points \(p_i\) and \(p_j\) is:

\[ d(p_i, p_j) = \sqrt{2 - (\epsilon_{i, j} + \epsilon_{j, i}) + (\epsilon_{i, 1} \epsilon_{j, 1} + \epsilon_{i, 2} \epsilon_{j, 2} + \dots + \epsilon_{i, N} \epsilon_{j, N})} \]

Here, if \(\epsilon_{i, j}\) is sufficiently small, the quadratic terms \((\epsilon_{i, 1} \epsilon_{j, 1}, \epsilon_{i, 2} \epsilon_{j, 2}, \dots, \epsilon_{i, N} \epsilon_{j, N})\) become much smaller and can be ignored when considering the order of distances. Thus, the condition can be seen as:

\[\sqrt{2 - (\epsilon_{A_1, B_1} + \epsilon_{B_1, A_1})} < \sqrt{2 - (\epsilon_{A_2, B_2} + \epsilon_{B_2, A_2})} < \dots < \sqrt{2 - (\epsilon_{A_{N(N-1)/2}, B_{N(N-1)/2}} + \epsilon_{B_{N(N-1)/2}, A_{N(N-1)/2}})}\]

To satisfy this, we can set, for example, \((\epsilon_{A_1, B_1}, \epsilon_{B_1, A_1}) = (-0.000001, 0), (\epsilon_{A_2, B_2}, \epsilon_{B_2, A_2}) = (-0.000002, 0), \dots\).

3. Final touches

The answer obtained in the previous step has issues like “coordinates are not integers” and “coordinates are not non-negative”.

This can be resolved by scaling and translating. For example, you could scale everything by \(10^6\) and then add \(\frac{N(N-1)}{2}\) to all coordinates uniformly. Such adjustments lead to the answer described at the beginning of this explanation.

---

Sample Solution

A C++ sample implementation is available at https://atcoder.jp/contests/arc172/submissions/50322419.

In Python, the solution can be implemented as follows:

# Receive input
n = int(input())
m = n * (n-1) // 2
a, b = [-1] * m, [-1] * m
for i in range(m):
    a[i], b[i] = map(lambda x: int(x)-1, input().split()) # Convert to 0-indexed

# Determine the order of distance for each pair of points
r = [[-1] * n for _ in range(n)]
for i in range(m):
    r[a[i]][b[i]] = m - i

# Determine the coordinates of the points
L = 10 ** 8
p = [
    [0 if i > j else L if i == j else r[i][j] for j in range(n)]
for i in range(n)]

# Output the answer
for i in range(n):
    print(*p[i])