B :: Persian Map

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Recently, archaeologists found some maps of Iran (formerly known as Persia). These maps belong to different dynasties and contain the name of the king of that time on top, like Keyumars, Bahram Chobin, Hushang, Jamshid, Kai Khosrow and many others. On each map there are some roads, each connecting exactly two cities. Some roads didn’t exist at a certain period of time (when they were not built yet or the road was covered in sand, blocked by a pile of dead soldiers who died in a great battle or washed away by a flood), so they might not exist in some maps. The good news is that today with the help of technology, archaeologists can dig the ground to find those roads. We know for sure that if at some point of time there existed some road between two cities, any road mentioned in earlier or later maps between the same cities is the same road. We now want to help the archaeologists find out how many roads can possibly be found.
You should merge the maps (add all the roads that existed on at least one map without adding the redundant roads) then count the number of roads.

Input

The input contains several test cases.
In the first line of input comes T (0 < T < 100), the number of test cases.
Each test case starts with n (0 < n < 10) and m (0 < m < 1000), the number of maps that the archaeologists found and the number of cities in Iran, respectively. Then comes the data for each map.
The map starts with the name of the king (without any spaces, at most 64 characters in length) and R (0 ≤ R < 1000), the number of roads in that map.
Then follows R lines. Line i contains two distinct integers x and y (0 ≤ x,y < m), the cities road i connects.

Output

For each test case, print a separate line containing the total number of roads that the archaeologists can find.

Sample Input

2
3 5
Hushang 3
0 1
1 2
2 3
Keyumars 4
0 1
1 3
2 1
4 3
KaiKhosrow 3
1 0
2 1
3 2
1 10
Jamshid 9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

Sample Output

5
9

Submit

Source: 12th Iran Nationwide Internet Contest - Final