Задача B. БАЗИ

В един град има N кръстовища, свързани с M еднопосочни улици. Трябва да се построят бази, от които излизат автомобили, патрулират по улиците и кръстовищата, след което се връщат, всеки в базата, от която е тръгнал. Напишете програма, която намира минималния брой улици, които ще останат необходени, както и да бъдат разположени базите.

Данните се въвеждат от стандартния вход. На първия ред е зададено цялото число T –броя на тестовите примери, организирани по следния начин: на първия ред на всеки тестов пример са зададени числата N и M (2£N£10000, 2£M£100000). Кръстовищата са номерирани с целите числа от 1 до N. На всеки от следващите M реда има по две числа U и V, което означава, че от кръстовище с номер U има улица към кръстовище с номер V.

Програмата трябва да изведе на отделни редове на стандартния изход T числа, търсения минимален брой необходени улици за всеки от тестовите примери..

ПРИМЕР

Вход Изход

2 1

10 12 0

1 2

2 3

2 4

3 1

4 5

4 7

5 6

6 3

7 8

8 9

9 10

10 7

2 2

1 2

2 1