Match The Following
In an examination, the students are given a match-the-following question. In the question, two sets of bubbles are listed on two sides. Some of the bubbles on the left will be joined to exactly one bubble on the right.
The students are asked to draw straight lines from the left set of bubbles to the right set of bubbles. You observe that none of the questions have answers in such a way that 3 or more lines are coincident. That is, there are two lines creating a point of intersection. Also, since the student doesn't know the answer to all questions, he might answer questions by skipping them. That is, he might just join the 4500th question with the 6th answer without answering the previous 4499 questions. Knowing the number of answered bubbles on both sides find the number of points of intersections.
1st line mentions the number of test cases that follow. The subsequent test cases are arranged as follows:
Topmost line for that test case is the number of answered bubbles on each side(n). After that the following n lines contain the correct matching as ordered pairs, for eg 2,1 means the 2nd bubble on the left is matched to the 1st bubble on the right. The bubble counting starts from the top with 1 being the topmost.
The output has T lines containing the number of intersections for each test case in order.
Input: 2 2 4 10 6 2 2 5 8 8 4 Output: 1 1
|Time Limit:||0.181667 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions