BRIDGE  Building Bridges
The tribe soon discovers that just communication is not enough and wants to meet each other to form a joint force against the terminator. But there is a deep canyon that needs to crossed. Points have been identified on both sides on which bridge ends can be made. But before the construction could be started, a witch Chudael predicted that a bridge can only be built between corresponding end points, i.e. a bridge starting from the i^{th} end point on one side can only end on the i^{th} end point on the other side, where the position of end points is seen in the order in which the points were identified. If not, it would lead to the end of the tribe. The tribe just wants to make as many noncutting bridges as possible, with the constraint in mind. Bridges "cut" if and only if they have exactly one common point that is not an end point.
Input
The first line of the input contains test cases t (1<=t<=50). It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n (1<=n<=10^{3}). The second line contains xcoordinates of end points identified on the first side and similiarly the third line contains the xcoordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The xcoordinates can range between 10^{3} to 10^{3}.
Output
You are required to output a single line for each test case. The line contains a single integer – the maximum number of bridges possible with the constraints explained above.
Example
Input:
34
2 5 8 10
6 4 1 2
3
5 3 10
6 4 1
6
1 2 3 4 5 6
3 4 5 6 1 2
Output:2
2
4
Expalanation: For the first test case, two nonoverlapping bridges can be formed between the 3rd and 4th end points on each side.
hide comments
kishanvadaliya:
20160624 17:03:17
what should be answer for this?


topke:
20160604 10:45:41
@Rohit Agarwal There is solution using BIT and using SegmentTrees. 

karthik1997:
20160603 09:19:55
Sorting and LIS(Longest increasing subsequence ) paves the way .. Just see the testcases and you will get the idea immediately ... And while finding LIS ,, for equal two points on second bridge , consider the first bridge coordinates too :p (I dont tell beyond this :p ) ,, and Expected complexity is O(n^2)..... Good Luck :D 

Rohit Agarwal:
20160601 12:45:31
Solved this problem with LIS but however the tag is binary search for this problem. In the beginning, I was trying to solve it with Binary Indexed tree but had some tc where it was printing wrong answers. Did anyone solved it using BS or BIT? Can someone please explain how to do it by that?


Akshay Damle:
20160421 20:09:17
The knapsacktype DP solution I thought of initially gave TLE :( n^2 LIS solution passed though 

try2catch:
20160322 07:09:04
I'm getting WA why?


Mateusz Lamecki:
20160114 14:23:04
@Shashank Tiwari: your post is very helpful, but actually answer of @Shubham Garg's test case is correct. 

Shashank Tiwari:
20151213 11:32:58
Let me explain the problem more clearly ....


e_coder:
20150623 13:37:41
try this one:


Sudarshan K:
20150531 14:03:06
No need to bang your head  O(n^2) passes :) 
Added by:  Troika::Bytes 
Date:  20100218 
Time limit:  0.193s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASMGCC AWK clang_c clang_cpp C++14 CLOJ COB dmd clang_d elixir F# fantom GO GROOVY JS2 nim NODEJS clang_objc objc PERL 6 pico PYPY PYTH 3.4 PYTH 3.2.3 n rust SCM chicken SED VB.net 