Sphere Online Judge

SPOJ Problem Set (classical)

6168. Building Bridges

Problem code: BRIDGE


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 ith†end point on one side can only end on the ith†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 non-cutting 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<=103). The second line contains x-coordinates of end points identified on the first side and similiarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified.†The x-coordinates can range between -103†to 103.

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:
3

4

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 non-overlapping bridges can be formed between the 3rd and 4th end points on each side.


Added by:Troika::Bytes
Date:2010-02-18
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: AWK CLOJ F# GO NODEJS PERL 6 PYTH 3.2.3 PYTH 3.2.3 n SED

hide comments
2014-09-02 21:30:12 GOKU
finally AC
2013-11-03 18:52:45 dunnohyet
more test cases plzz
2013-09-14 11:37:40 shalini pandey
Plz suggest more test cases . Getting wa :(
2013-06-22 20:00:38 Charu
Please suggest more test cases...
2013-06-13 03:10:25 Abhishek Kumar
*"Bridges "cut" if and only if they have exactly one common point that is not an end point."*
what does it mean ??
2013-06-12 00:33:58 Kushagara
@Troika::Bytes: Please do look at the submission 9462513 getting WA tried many test cases still:(
2013-04-27 13:14:11 Alex Abbas
after solving this problem try: BRDGHRD
2011-09-29 13:30:01 NoszŠly Csaba
strange interpretation of overlapping-ness.
the situ of "bridges with both end-points the same" does occur in test cases.

Last edit: 2013-04-27 20:28:50
2011-02-24 20:54:07 :D
I don't know if that situation occurs in test cases, but my AC program would also consider bridges with both end-points the same as NOT overlapping.

Last edit: 2011-02-25 06:25:53
2011-02-12 21:06:23 Anshu Saurabh
Should consider two bridges having same end point are non-overlapping.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.