Reconstruction of a set from a pair partition This may be a classical problem, but I wasn't able to find out any info about it:

Let $n$ be a positive integer and $M:=\{-n,-n+1,...,-1,1,2,...,n\}$. We form $n$ unordered pairs, denoted $P_i, i=\overline{1,n}$, with the numbers in $M$, in an arbitrary manner. Prove or disprove that from each pair $P_i$, we can choose a number $a_i$ such that $\{|a_i|/i=\overline{1,n}\}=\overline{1,n}$.

Intuitively, it seems to be true, I haven't found a counter-example. What I realized is that we can neglect the pairs $(x,-x)$, in this way we reduce to the case with $n-1$ pairs.
Example: $M=\{-5,-4,-3,-2,-1,1,2,3,4,5\}$, the pairs are $P_1=(-1,3), P_2=(-2,1), P_3=(2,-4), P_4=(-3,-5), P_5=(4,5)$. We can choose $a_1=3, a_2=1, a_3=2, a_4=-5, a_5=4$.
I found this question, which is very similar, but still no clue how to link to my problem. Maybe there is something trivial I don't see. Thank you!
 A: As you said, we can assume without loss of generality that $x$ is never paired with $-x$.
A similar idea to the question you linked works. Consider the graph whose vertices are $\{1,\dots,n\}$, where for each pair $\{v,w\}$, there is an edge joining $|v|$ to $|w|$. We allow multiple edges; when both the pairs $\{2,-3\}$ and $\{3,-2\}$ appear, $2$ and $3$ would be connected by two edges.
For every $v\in \{1,\dots,n\}$, there will be exactly two edges out of $v$, one for the pair containing $v$ and the other for the pair containing $-v$. This means the graph is two-regular, and can therefore be partitioned into cycles. Give each cycle an orientation. Each directed edge $v\to w$ in a cycle comes from some pair $\{\pm v,\pm w\}$. A successful selection is then given by choosing $\pm v$ for each directed edge $v\to w$.
In your example, the graph is
1 ——— 3 
|      \
|       5
|      /  
2 ——— 4 

Orient this cycle clockwise. The edge connecting $1$ to $3$ came from the pair $\{-1,3\}$; since $1$ points to $3$ in our orientation, we choose $-1$ from that pair. The edge connecting $3$ to $5$ came from  $\{-3,-5\}$, so we select $-3$ from that pair. Continuing on in this fashion, the selection is
$$
\{-1,3\}\to 1\\
\{-3,-5\}\to -3\\
\{4,5\}\to 5\\
\{2,-4\}\to -4\\
\{-2,1\}\to -2
$$
