MSTICK - Wooden Sticks
Tác giả: ladpro98
Ngôn ngữ: Pascal
program mstick;
uses math;
type e=record
l,r:longint;
end;
const fi='';
maxN=5555;
var b:array[1..maxN] of e;
a,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,b[i].l,b[i].r);
end;
procedure swap(i,j:longint);
var t:e;
begin
t:=b[i];
b[i]:=b[j];
b[j]:=t;
end;
procedure sort(l,r:longint);
var p:e;
i,j:longint;
begin
if l>=r then exit;
p:=b[random(r-l+1)+l];
i:=l;j:=r;
repeat
while (b[i].l<p.l) or ((b[i].l=p.l) and (b[i].r<p.r)) do inc(i);
while (b[j].l>p.l) or ((b[j].l=p.l) and (b[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;
procedure init;
var i:longint;
begin
for i:=1 to n do
a[i]:=b[i].r;
end;
function find(r,key:longint):longint;
var l,m,k:longint;
begin
l:=1;
while l<=r do
begin
m:=(l+r) shr 1;
if a[f[m]]<=key 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]>=a[f[1]] then f[1]:=i
else
if a[i]<a[f[d]] 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);
init;
dp;
writeln(d);
end;
end.