Nothing in Common || Easy Problem

      No Comments on Nothing in Common || Easy Problem

Nothing In Common between Alice and Berta Problem Statement

Alice has quarreled with Berta recently. Now she wants to have nothing in common with her!Recently, they’ve received two collections of positive integers. The Alice’s integers were A1A2, …, AN, while Berta’s were B1B2, …, BM.

Now Alice wants to throw away the minimal amount of number from her collection so that their collections would have no common numbers, i.e. there won’t be any number which is present in both collections. Please help Alice to find the minimal amount of numbers she would need to throw away.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integer numbers N and M denoting the number of numbers in Alice’s and Berta’s collections respectively.

The second line contains N space-separated integers A1A2, …, AN denoting the numbers of Alice.

The third line contains M space-separated integers B1B2, …, BM denoting the numbers of Berta.

Output

For each test case, output a single line containing the minimal amount of numbers Alice needs to throw away from her collection so that she wouldn’t have any numbers in common with Berta.

Constraints

  • 1 ≤ AiBi ≤ 106
  • All numbers are distinct from a single girl’s collection.

Subtasks

  • Subtask #1 (47 points)T = 251 ≤ N, M ≤ 1000
  • Subtask #2 (53 points)T = 51 ≤ N, M ≤ 100000

Example

Input:
2
3 4
1 2 3
3 4 5 6
3 3
1 2 3
4 5 6

Output:
1
0

Explanation

Example case 1. If Alice throws away the number 3 from her collection, she would obtain {1, 2} which is disjoint with {3, 4, 5, 6}.

Example case 2. Girls don’t have any number in common initially. So there is no need to throw away any number

QUICK EXPLANATION:

Since all numbers within A are distinct and also all elements within Bare distinct, A and B are set. What we want to do is to remove the minimum number of elements from in such a way that A and do not have any common elements. In other words, it means that we want to make their intersection empty, which means that if C is the intersection of A and B, we have to remove all elements of C and there is no need to remove any other elements. Thus the problem is reduced to finding the size of the intersection of A and B. Depending on the subtask below methods are possible.

Subtask 1

In this subtask, we know that each A and B have at most 1000 elements each and there are at most 25 test cases to handle. This allows us to iterate over all elements of A, and for each one perform a full scan of elements of B to check if the element belongs to both sets. For a single test case, this method results in O(|A||B|) time complexity.

Subtask 2

In the second subtask, Aand B can have up to 105 elements, which makes the above approach too slow. However, one can use a hash map to count the number of occurrences of all elements from A and B together. It follows that each element belongs to the intersection of A and B if and only if its count is equal to 2. This approach has O(|A|+|B|)time complexity per single test case. It is worth to mention that since all input elements are positive integers not greater than 106, one can use a simple array instead of a hashmap to compute the counters, which results in a similar time complexity and perhaps even easier implementation.

To know more https://www.codechef.com/problems/NOTINCOM

{Code With Code@ter}

Give Your Reviews

Leave a Reply