Математикадан облыстық олимпиада, 2005-2006 оқу жылы, 9 сынып

Мемлекетте аралары жолдармен қосылған бірнеше қала бар. Әрбір жол тек екі қаланы қосады және онда біржақты қозғалыс енгізілген; оған қоса қала жұптары бірден көп емес жолдармен қосылған. Кез келген қаладан шығып ол қалаға қайта оралуға болмайды. $A$ қаласынан $B$ қаласына дәл 2006 тәсілмен жетуге болады. Мемлекетте ең аз дегенде қанша қала болатынын анықтаңыздар.