CF1474E What Is It?

给定一个 $n$，你需要构造一个排列 $\{p_i\}$ 和一个操作序列。 每次操作你可以交换 $i$ 位置和 $j$ 位置的值，要求 $i\ne j$ 且 $i = p _ j$，并获得 $(j-i)^2$ 的贡献。 要求最后满足 $p_i = i$。 你需要最大化总贡献。 可以证明，操作次数 $

多组数据，每组数据给定一个 $n$。

首先，第一行一个数，表示你求出的最大贡献。 然后第二行给出你构造的 $\{p_i\}$。 第三行给出一个数 $m$，表示你需要的操作次数。 接下来 $m$ 行，每行两个数，代表当前操作的 $i$ 和 $j$（注意，**有顺序要求**） translate by peal_frog

For $ n = 2 $ , $ p $ can be either $ [1, 2] $ or $ [2, 1] $ . In the first case $ p $ is already identity, otherwise robot will make it an identity permutation in $ 1 $ second regardless of choise $ i $ and $ j $ on the first operation. For $ n = 3 $ , $ p $ can be equals $ [2, 3, 1] $ . - If robot will select $ i = 3, j = 2 $ on the first operation, $ p $ will become $ [2, 1, 3] $ in one second. Now robot can select only $ i = 1, j = 2 $ or $ i = 2, j = 1 $ . In both cases, $ p $ will become identity in one more second ( $ 2 $ seconds in total). 4. If robot will select $ i = 1, j = 3 $ on the first operation, $ p $ will become $ [1, 3, 2] $ in four seconds. Regardless of choise of $ i $ and $ j $ on the second operation, $ p $ will become identity in five seconds. We can show, that for permutation of length $ 3 $ robot will always finish all operation in no more than $ 5 $ seconds.