Олимпиада Туймаада по математике. Младшая лига. 2016 год

На карте полетов авиакомпании $K_{r,r}$ изображены несколько городов, некоторые пары городов связаны прямым (двусторонним) авиарейсом, причем всего имеется $m$ авиарейсов. Требуется выбрать две непересекающиеся группы по $r$ городов в каждой такие, что каждый город одной группы связан авиарейсом с каждым из городов второй группы. Докажите, что этот выбор можно осуществить не более чем $2 m^r$ способами. ( D. Conlon )