Íŕçŕä ę ëó÷řčě đĺřĺíč˙ě Status: AC, problem ZELC, contest ZEL07. By tourist (Gennady Korotkevitch), 2007-03-10 11:41:45.
{$R-,S-,Q-,I-,O+}
var
  uu,kol,z,u,q,n,qq,tt,i: longint;
  sumx,sumy,tmp,min,xx,yy: single;
  key,x,y: array [0..3010] of single;
  pr,ne,pred: array [0..3010] of longint;
begin
  read(tt);
  for qq:=1 to tt do
  begin
    read(n);
    for i:=1 to n do read(x[i],y[i]);
    for q:=1 to n do key[q]:=1000000000;
    for i:=0 to n+1 do
    begin
      pr[i]:=i-1;
      ne[i]:=i+1;
    end;
    key[1]:=0; pred[1]:=0;
    u:=1;
    for q:=1 to n-1 do
    begin
      ne[pr[u]]:=ne[u];
      pr[ne[u]]:=pr[u];
      uu:=u;
      min:=1000000001; u:=0;
      i:=ne[0];
      while i <= n do
      begin
        tmp:=sqr(x[i]-x[uu])+sqr(y[i]-y[uu]);
        if tmp < key[i] then
        begin
          key[i]:=tmp;
          pred[i]:=uu;
        end;
        if key[i] < min then
        begin
          min:=key[i];
          u:=i;
        end;
        i:=ne[i];
      end;
    end;
    writeln(0);
    writeln(n-1);
    for i:=2 to n do writeln(pred[i]-1,' ',i-1);
  end;
end.