Marinada '17

U nekoj državi postoji $128$ gradova, a između nekih parova gradova prometuju direktne dvosmjerne avionske linije (najviše jedna linija između svaka dva grada), pri čemu svaka linija pripada jednoj od dviju kompanija. Odredi najmanji prirodan broj $m$ takav da vrijedi sljedeće: Ako ukupno postoji barem $m$ avionskih linija, sigurno je moguće napraviti kružno putovanje koje posjećuje točno $3$ ili $5$ gradova, a koristi linije samo jedne kompanije.