MDOLLS - Nested Dolls
Tác giả: ladpro98
Ngôn ngữ: Pascal
uses math;
type e=record
l,r:longint;
end;
const fi='';
maxN=22222;
var a:array[1..maxN] of e;
f:array[1..maxN] of longint;
tt,t,n,d:longint;
inp:text;
procedure openF;
begin
assign(inp,fi);
reset(inp);
readln(inp,t);
end;
procedure input;
var i:longint;
begin
readln(inp,n);
for i:=1 to n do
read(inp,a[i].l,a[i].r);
end;
procedure swap(i,j:longint);
var t:e;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure sort(l,r:longint);
var p:e;
i,j:longint;
begin
if l>=r then exit;
p:=a[random(r-l+1)+l];
i:=l;j:=r;
repeat
while (a[i].l<p.l) or ((a[i].l=p.l) and (a[i].r>p.r)) do inc(i);
while (a[j].l>p.l) or ((a[j].l=p.l) and (a[j].r<p.r)) do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;
function find(r:longint; key:e):longint;
var l,m,k:longint;
begin
l:=1;
while l<=r do
begin
m:=(l+r) shr 1;
if (a[f[m]].l<key.l) and (a[f[m]].r<key.r) then
begin
k:=m;
r:=m-1;
end
else l:=m+1;
end;
exit(k);
end;
procedure dp;
var i:longint;
begin
f[1]:=1;
d:=1;
for i:=2 to n do
begin
if (a[i].r<=a[f[d]].r) or (a[i].l<=a[f[d]].l) then
begin
inc(d);
f[d]:=i;
end
else
f[find(d,a[i])]:=i;
end;
end;
begin
openF;
for tt:=1 to t do
begin
input;
sort(1,n);
dp;
writeln(d);
end;
end.