Croatian Mathematical Olympiad 2022 Problem M-2

Neka je $n$ prirodan broj. U selu živi $2n$ ljudi. Neki među njima su su prijatelji, a prijateljstva su uzajamna. Savršeno sparivanje je podjela stanovnika sela na $n$ parova tako da su u svakom paru dvije osobe koje su prijatelji.

Pretpostavimo da u selu postoji točno jedno savršeno sparivanje. Koji je najveći mogući broj prijateljstava u selu?