Croatian Mathematical Olympiad 2015 Problem I-2

U nekoj državi je $N$ gradova, među nekima postoje (dvosmjerne) avionske linije. Svaki let povezuje točno dva grada. Nijedan grad nije povezan izravnim letovima sa svim ostalim gradovima. Poznato je da za svaka dva grada $A$ i $B$ postoji točno jedan način da se dođe iz $A$ u $B$ koristeći najviše dva leta. Dokaži da je $N - 1$ kvadrat prirodnog broja.