Cancel the Trains
Contest: Codeforces Round 688 (Div. 2)
Difficulty rating: 800
Tags: implementation

Gildong's town has a train system that has $$$100$$$ trains that travel from the bottom end to the top end and $$$100$$$ trains that travel from the left end to the right end. The trains starting from each side are numbered from $$$1$$$ to $$$100$$$, respectively, and all trains have the same speed. Let's take a look at the picture below.

The train system can be represented as coordinates on a 2D plane. The $$$i$$$-th train starting at the bottom end is initially at $$$(i,0)$$$ and will be at $$$(i,T)$$$ after $$$T$$$ minutes, and the $$$i$$$-th train starting at the left end is initially at $$$(0,i)$$$ and will be at $$$(T,i)$$$ after $$$T$$$ minutes. All trains arrive at their destinations after $$$101$$$ minutes.

However, Gildong found that some trains scheduled to depart at a specific time, simultaneously, are very dangerous. At this time, $$$n$$$ trains are scheduled to depart from the bottom end and $$$m$$$ trains are scheduled to depart from the left end. If two trains are both at $$$(x,y)$$$ at the same time for some $$$x$$$ and $$$y$$$, they will crash into each other. Therefore, he is asking you to find the minimum number of trains that should be cancelled to prevent all such crashes.

Input format:
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$).

Each test case contains three lines. The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — the number of trains scheduled to depart from the bottom end, and the number of trains scheduled to depart from the left end, respectively.

The second line of each test case contains $$$n$$$ integers. Each integer is a train number that is scheduled to start from the bottom end. The numbers are given in strictly increasing order, and are between $$$1$$$ and $$$100$$$, inclusive.

The third line of each test case contains $$$m$$$ integers. Each integer is a train number that is scheduled to start from the left end. The numbers are given in strictly increasing order, and are between $$$1$$$ and $$$100$$$, inclusive.

Output format:
For each test case, print a single integer: the minimum number of trains that should be canceled in order to prevent all crashes.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first case, we can show that there will be no crashes if the current schedule is followed. Therefore, the answer is zero.

In the second case, at $$$T=4$$$, there will be a crash, as can be seen in the picture below. We can prove that after canceling one of these trains, the remaining trains will not crash. Therefore, the answer is one.

Example input:
3
1 2
1
3 4
3 2
1 3 4
2 4
9 14
2 7 16 28 33 57 59 86 99
3 9 14 19 25 26 28 35 41 59 85 87 99 100

Example output:
0
1
3

Editorial:
Let's first determine whether it's possible for two trains that start from $$$(i,0)$$$ and $$$(0,j)$$$ to crash into each other. For this to happen, there must be a point where $$$(i,T)=(T,j)$$$, which means $$$i=T$$$ and $$$j=T$$$. Therefore, a train that starts from the bottom end can crash into a train that starts from the left end if and only if they have the same train number. We can cancel either one of them to prevent that crash.
Since $$$n$$$ and $$$m$$$ are small, we can brute-force every pair of trains and count the number of pairs of trains that share the same number, and print that value as the answer. The time complexity for this solution is $$$\mathcal{O}(nm)$$$ for each test case.
If we want an asymptotically faster solution, we can put all train numbers into a binary search tree structure (such as std::set in C++), and then find duplicate numbers from the trains of the other side by searching for those values. Another similar solution is to sort the former numbers, then perform binary search for the other values. The time complexity for these solutions is $$$\mathcal{O}((n+m)\log(n))$$$.
There is another solution with $$$\mathcal{O}(n+m)$$$ time complexity taking advantage of the fact that the train numbers are small. Let's make an array $$$X$$$ of length $$$101$$$, and set $$$X[i] = true$$$ if and only if there is a train starting from $$$(i, 0)$$$. For each train starting from $$$(0, j)$$$, we can check if $$$X[j]$$$ is $$$true$$$, and count the total number of duplicates this way.