Sejal wants to have a get-together with her friends, as she had had last year. She has n friends and each of them came to her house and stayed for a specific range of days of the year from si(start date) to ei(end date), the previous year. Last year, all the people who met each other became friends and had exchanged their contact details.
Person A met Person B, if and only if Person A's start date was on or before Person B's end date, or vice-versa.
This year she is too tired of contacting each of her friends individually for their approval, so she thinks of a strategy. She tries to contact minimum no:of friends, and tells them to pass on the invitation to all their respective friends.
Sejal wants to know the minimum no:of friends she needs to contact, so that all the 'n' friends receive her invitation directly or indirectly. Help Sejal in getting her work done.
- The first line of the input contains a single integer "t" — the number of testcases.
- The second line of the input contains a single integer "n" — the number of Sejal's friends.
- Then follow n lines, that describes the friends' start and end date. Each of n lines contain two space-separated integers si and ei , providing that the ith friend can come to her house from day si to day ei inclusive (both inclusive)
For each test case, the output the minimum no:of friends to be contacted in order to reach out to all the 'n' friends, in a new line.
- 1 ≤ t ≤ 2000
- 1 ≤ n ≤ 10^5
- 1 ≤ si ≤ ei≤ 10^5
- 1 ≤ sum of "n" over all test cases ≤ 6*10^5
Input: 1 4 151 307 307 352 117 145 24 128 Output: 2
Example case 1.1st and 2nd person become friends, on the other side 3rd and the 4th one become friends. Sejal can call up one between 1st and 2nd person, and the other between 3rd and the 4th( 1,3 or 1,4 or 2,3 or 2,4). In all the cases, minimum answer will be 2.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, PHP, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, PERL6, CLOJ, FS|
Fetching successful submissions