Minimum Number Of People To Teach

Ninja has started a social networking site called Ninjas Space. The platform consists of ‘N’ users and supports ‘M’ different languages. Users communicate if they know at least one common language. There are ‘L’ friendships among users on this network.

You are provided with a 2D array called ‘LANGUAGES’ which has ‘N’ rows and ‘M’ columns, where LANGUAGES[i][j] == 1 indicates user i+1 knows language j+1. Otherwise, it is 0. Additionally, a 2D array ‘FRIENDS’ of size ‘L’ is given, where each row represents a pair of friends. The task is to determine the minimum number of users Ninja needs to teach a common language so all friends can communicate.

Input:

The first line of input contains an integer, 'T', representing the number of test cases.

For each test case:

The first line contains three space-separated integers, 'N', 'M', and 'L'. 

Each of the next 'N' lines contains 'M' space-separated integers for the 'LANGUAGES' array.

Each of the next 'L' lines contains two space-separated integers for the 'FRIENDS' array.

Output:

For each test case, output the minimum number of users Ninja needs to teach.

Example:

'LANGUAGES' = [[1,0,1],[0,0,1],[0,1,0]], 'FRIENDS' =[[1,3],[2,3]]

Ninja can teach the third language to the third user so all friends can communicate with each other. Thus, the result is 1.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 500
• 1 <= M <= 500
• 1 <= L <= 500
• 1 <= FRIENDS[i][0], FRIENDS[i][1] <= N
• FRIENDS[i][0] != FRIENDS[i][1]
• LANGUAGES[i][j] values are either 0 or 1
• All entries in 'FRIENDS' are unique

Time limit: 1 second.