Ученическо състезание по програмиране
27 март 2004 г., Благоевград

Задача H. Годината е 2045. Хората вече знаят, че не са сами... . Още през далечната 2021 г. те осъществили близка среща от трети вид със същества от планетата Марс. От началото двете раси се разбирали добре. Но настъпил момент в които отношенията им се развалили. Така започнала и първата междупланетна война. На 3 юли 2045г. марсианците успели да извършат своята най-мащабна операция и разрушили десетте най-големи града на Земята. Единствения скрит коз на хората в този момента е специалната група “СИГМА” създадена още в началото на войната. Групата се състои от хакери, кракери и програмисти. Хакерите са хакнали един от най-големите марсиански сървъри и са успели да източат някаква информация. За съжаление те не знаят какво са изтеглили и го предават на кракерите. Кракерите от своя страна откриват за какво служи информацията, която хакерите са изтеглили. Информацията се състои от файлове. Като всеки файл съответства на един голям град от Марс. На първия ред от всеки файл има по едно число 0<n<21, което показва броя на най-важните сървъри, които се намират в даден град. Те са номерирани с числата от 1 до n. На следващите няколко реда са записани по две числа 0<p<7, където p e от вида (2k) и  0<=q<=1018. Все пак най-накрая кракерите разбират за какво служат тези числа. Ако от номерата на сървърите образуваме групи от по p числа, то числото q е поредния номер на една от тези групи. Даден сървър не може да присъства повече от веднъж в група. (Като групите са подредени във възходящ ред и най-малката от тях е с номер 0). Сървърите могат да имат връзка помежду си и обменят всякаква информация. Това, че два сървъра са свързани помежду си можете да разберете от подребата им в дадената група. Връзка има между всеки два, като връзката е еднопосочна и е от първия към втория. Вашата задача е да помогнете на програмистите да напишат програма, която да извежда най–малкия брой сървъри, на които трябва да се сложи вирус за да може да бъде разрушена цялата система от сървъри на марсианците. Ако се сложи вирус на даден компютър той достига до всички компютри, до които може да достигне по мрежата и разрушава всичката информация на тях. Така ще бъде блокирана защитната система на тези градове и хората ще могат лесно да нападнат и да унищожат тези градове. 

 Вход:                                   
 На първия ред е записан броят на тестовите примери. Следват тестовите примери, структурирани по следния начин:
  1 ред: Число n
  Следващите няколко реда са от вида : p q 
  Тестовият пример завършва с:  –1

Изход:         
За всеки тестов пример изходът съдържа по един ред, на който се отпечатва цяло число k (Броя на намерените сървъри на който трябва да се качи вирус)

Пример: 
  Вход				       Изход         
1  
3                     2
2 4                                                  
–1