Croatian Mathematical Olympiad 2020 Problem 1-2

Ante je zapisao niz $a_1, a_2, \ldots, a_{2020}$ u kojem se svaki od brojeva $1, 2, \ldots, 2020$ pojavljuje točno jednom. Barbara želi saznati taj niz, a Ante joj daje informacije kroz niz razmjena.

U jednoj razmjeni Barbara na papir zapiše brojeve od $1$ do $2020$ te neke od njih spoji crtom i to tako da je svaki broj spojen s najviše jednim drugim i preda taj papir Anti. Ante zatim na drugi papir zapiše brojeve od $1$ do $2020$ te za svaki par brojeva $i$ i $j$ koje je Barbara spojila crtom, on spoji crtom brojeve $a_i$ i $a_j$, te na kraju preda taj papir Barbari.

Koliko je najmanje razmjena potrebno da Barbara može sa sigurnošću odrediti Antin niz?