В исследовательских целях, $$$n^2$$$ лабораторий были построены на горе на различных высотах. Давайте пронумеруем их целыми числами от $$$1$$$ до $$$n^2$$$, так что лаборатория с номером $$$1$$$ находится в самом низком месте, лаборатория с номером $$$2$$$ находится во втором по высоте месте, $$$\ldots$$$, лаборатория с номером $$$n^2$$$ находится в самом высоком месте.

Для транспортировки воды между лабораториями, трубы были построены между всеми парами лабораторий. Труба может переместить не больше одной единицы воды в единицу времени из лаборатории с номером $$$u$$$ в лабораторию с номером $$$v$$$, если $$$u > v$$$.

Сейчас необходимо разбить лаборатории на $$$n$$$ групп, каждая группа должна содержать ровно $$$n$$$ лабораторий. Лаборатории из разных групп могут транспортировать воду друг другу. Тогда суммарное количество воды, которое может быть отправлено из группы $$$A$$$ в группу $$$B$$$ равно количеству пар лабораторий ($$$u, v$$$), таких что лаборатория с номером $$$u$$$ из группы $$$A$$$, лаборатория с номером $$$v$$$ из группы $$$B$$$ и $$$u > v$$$. Давайте обозначим это число за $$$f(A,B)$$$ (то есть $$$f(A,B)$$$ равно суммарному количеству воды, которое может быть отправлено из группы $$$A$$$ в группу $$$B$$$).

Например, если $$$n=3$$$ и есть $$$3$$$ группы $$$X$$$, $$$Y$$$ и $$$Z$$$: $$$X = \{1, 5, 6\}, Y = \{2, 4, 9\}$$$ и $$$Z = \{3, 7, 8\}$$$. В этом случае значения $$$f$$$ равны:

• $$$f(X,Y)=4$$$ потому что $$$5 \rightarrow 2$$$, $$$5 \rightarrow 4$$$, $$$6 \rightarrow 2$$$, $$$6 \rightarrow 4$$$,
• $$$f(X,Z)=2$$$ потому что $$$5 \rightarrow 3$$$, $$$6 \rightarrow 3$$$,
• $$$f(Y,X)=5$$$ потому что $$$2 \rightarrow 1$$$, $$$4 \rightarrow 1$$$, $$$9 \rightarrow 1$$$, $$$9 \rightarrow 5$$$, $$$9 \rightarrow 6$$$,
• $$$f(Y,Z)=4$$$ потому что $$$4 \rightarrow 3$$$, $$$9 \rightarrow 3$$$, $$$9 \rightarrow 7$$$, $$$9 \rightarrow 8$$$,
• $$$f(Z,X)=7$$$ потому что $$$3 \rightarrow 1$$$, $$$7 \rightarrow 1$$$, $$$7 \rightarrow 5$$$, $$$7 \rightarrow 6$$$, $$$8 \rightarrow 1$$$, $$$8 \rightarrow 5$$$, $$$8 \rightarrow 6$$$,
• $$$f(Z,Y)=5$$$ потому что $$$3 \rightarrow 2$$$, $$$7 \rightarrow 2$$$, $$$7 \rightarrow 4$$$, $$$8 \rightarrow 2$$$, $$$8 \rightarrow 4$$$.

Пожалуйста, разбейте лаборатории на $$$n$$$ групп размера $$$n$$$, так что значение $$$\min f(A,B)$$$ по всем возможным парам групп $$$A$$$ и $$$B$$$ ($$$A \neq B$$$) было максимально.

Другими словами, разбейте лаборатории на $$$n$$$ групп размера $$$n$$$, таких что минимальное количество воды, которое может быть отправлено из группы $$$A$$$ в группу $$$B$$$ для всех возможных пар групп $$$A$$$ и $$$B$$$ ($$$A \neq B$$$) было максимально большое.

Обратите внимание, что приведенный в условии пример не демонстрирует оптимальное разбиение на группы, он демонстрирует подсчет значений $$$f$$$ для некоторого разбиения.

Если существует несколько оптимальных разбиений, вы можете найти любое.