Problem J
Where is the ‘back’ button?
Input: Standard Input

Output: Standard Output

 

The employees of the ‘Dendrogram Workless Inc.’ do their tasks through a local intranet application with web page like interface. Every single worker has a designated homepage with all his tasks. According to the company’s new security policy, no worker is allowed to visit any other personnel’s homepage. But the old pages might contain some links to other pages (or even a link to itself.) Instead of removing links from working pages, they introduce a new web browser without the ‘back’ button and make the employees use this new browser. The idea is, no employee can leave his designated page because without a ‘back’ button there is no assurance that a worker will find a path to return to his home page just when the boss comes in! The employees soon get bored and decide that they would like to visit other pages. So, they plan to insert new links as necessary to their pages so that every single employee can return to his home page after clicking one or more links without using the ‘back’ button. You are to help them by finding the minimum number of links to insert.

 

Input

The first line of the input states the number of test cases in the input. Each test case begins with two integers – The number of pages in the system, P (1 ≤ P ≤ 20) & The number of links, L (0 ≤ L ≤ (P * (P-1)/2)). The pages are denoted by integers from 0 to P-1. Each of the next L lines contains two integers A & B (1 ≤ A,B ≤ P) implying that page A has a link to page B.

 

Output

For each test case, print the minimum number of links to be inserted.

 

Sample Input                              Output for Sample Input

2

5 5

0 2

2 1

2 4

3 0

4 0

4 6

1 2

1 3

2 0

3 2

3 0

0 1

 

1

0

 

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks: Abdullah al Mahmud