CF1508D Swap Pass

Based on a peculiar incident at basketball practice, Akari came up with the following competitive programming problem! You are given $ n $ points on the plane, no three of which are collinear. The $ i $ -th point initially has a label $ a_i $ , in such a way that the labels $ a_1, a_2, \dots, a_n $ form a permutation of $ 1, 2, \dots, n $ . You are allowed to modify the labels through the following operation: 1. Choose two distinct integers $ i $ and $ j $ between $ 1 $ and $ n $ . 2. Swap the labels of points $ i $ and $ j $ , and finally 3. Draw the segment between points $ i $ and $ j $ . A sequence of operations is valid if after applying all of the operations in the sequence in order, the $ k $ -th point ends up having the label $ k $ for all $ k $ between $ 1 $ and $ n $ inclusive, and the drawn segments don't intersect each other internally. Formally, if two of the segments intersect, then they must do so at a common endpoint of both segments. In particular, all drawn segments must be distinct. Find any valid sequence of operations, or say that none exist.

N/A

N/A

The following animation showcases the first sample test case. The black numbers represent the indices of the points, while the boxed orange numbers represent their labels.  In the second test case, all labels are already in their correct positions, so no operations are necessary.