SP14742 BRDGHRD - Building Bridges(HARD)

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 non-overlapping bridges as possible, with the constraint in mind. ### Input The first line of the input contains test cases t. 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/A

N/A