Give me test data

I got AC with a somehow optimized backtracking that generated partitions for N. When I reached a partition with K critical edges -> solution. But with a value of K well chosen (maximum K for which we do not have all pairs critical) this approach should TLE.
Test is N = 100, K = 4947

Please add this test:
100 4950

On my computer my solution works 1.68sec, but I got AC with 1 sec.

the graph is simple!!!
input:
2 0

output:
-1

GOOD LUCK!!!

[code deleted]

Edited by moderator 28.07.2006 10:35

I have Fail (Validator) on Test#5 using CPP. Submit ID is 892128. What is the problem?

Program is Here:

 Program Ural1169(Input,Output);
 Const
      MaxN=100;
 Type
      IntTypeNum1=Longint;
      IntTypeNum3=Shortint;
      SolutionType=array [1..MaxN] of IntTypeNum1;
 Var
      n,k,Total:IntTypeNum1;
      Found:Boolean;
      Sol:SolutionType;
 Procedure Init;
    begin
      readln(n,k);
    end;
 Procedure Search(Left,Need:IntTypeNum1);
    var
      l,Temp:IntTypeNum1;
    begin
      if Need=0 then
        begin
          Found:=True;
          Exit;
        end;
      if Left*(Left-1) div 2<Need then Exit;
      for l:=3 to Left do
        begin
          Temp:=l*(l-1) div 2;
          inc(Total);
          Sol[Total]:=l;
          if Need>=Temp then Search(Left-l,Need-Temp)
            else
              begin
                dec(Total);
                Break;
              end;
          if Found then Exit;
          dec(Total);
        end;
    end;
 Procedure Main;
    var
      i,L1,L2,Cur:IntTypeNum1;
    begin
      if (n=1) and (k=0) then Exit;
      if n=2 then
        begin
          if k=0 then writeln(-1);
          if k=1 then writeln(1,' ',2);
          Exit;
        end;
      Found:=False;
      Total:=0;
      Search(n,n*(n-1) div 2-k);
      if not Found then
        begin
          writeln(-1);
          Exit;
        end;
      Cur:=0;
      for i:=1 to Total do
        begin
          if i<>1 then writeln(1,' ',Cur+1);
          for L1:=Cur+1 to Cur+Sol[i] do
            for L2:=L1+1 to Cur+Sol[i] do writeln(L1,' ',L2);
          inc(Cur,Sol[i]);
        end;
      for L1:=Cur+1 to n do writeln(1,' ',L1);
    end;
 Begin
      Init;
      Main;
 End.

And I got WA on Test 18!
How 郁闷 I am!!!(Who can Translate the Chinese to English...)
Please help me. Thanks.

Who can explain me the problem ????????

My programme is:

const nnn=100;
var n,k,b,c,d,f:integer;
    a:array[1..nnn,0..(nnn-1)*nnn div 2] of shortint;
    e:array[1..100] of integer;
begin
  readln(n,k);
  k:=n*(n-1) div 2-k;
  for b:=1 to n do e[b]:=(b-1)*b div 2;
  for b:=1 to n do begin
    for c:=0 to e[n] do a[b,c]:=-1;
    a[b,e[b]]:=0;
  end;
  for b:=1 to n do
    for c:=0 to e[b]-1 do
      for f:=b-1 downto 1 do begin
        d:=f;
        if c<e[b-d] then break;
        if a[d,c-e[b-d]]>=0 then begin
          a[b,c]:=d; break;
        end;
      end;
  if a[n,k]<0 then writeln(-1) else
    while n>0 do begin
      for b:=a[n,k]+1 to n-1 do writeln(b,' ',b+1);
      if a[n,k]+1<>n then writeln(n,' ',a[n,k]+1);
      if a[n,k]<>0 then writeln(a[n,k],' ',a[n,k]+1);
      b:=k; dec(k,e[n-a[n,k]]); n:=a[n,b];
    end;
end.

{This is my program}
program p1169;

const
  maxn=100;
  maxd=maxn*(maxn-1) div 2;

var
  d,f:array [0..maxd] of longint;
  b:array [1..maxn] of longint;
  n,e,i,delta,j,k,p,tail,top:longint;

begin
  read(n,e);
  e:=(n*(n-1) div 2)-e;

  for i:=0 to maxd do d[i]:=maxlongint;
  fillchar(f,sizeof(f),0);
  d[0]:=0;
  for i:=3 to maxn do
  begin
    delta:=i*(i-1) div 2;
    for j:=maxd downto 0 do
      if d[j]<>maxlongint then
      begin
        k:=j+delta; p:=d[j]+i;
        while k<=maxd do
        begin
          if p<d[k] then
          begin
            d[k]:=p;
            f[k]:=i;
          end;
          k:=k+delta; p:=p+i;
        end;
      end;
  end;

  if d[e]>n then
  begin
    writeln(-1);
    exit;
  end;

  tail:=0;
  i:=e;
  while i>0 do
  begin
    inc(tail); b[tail]:=f[i];
    i:=i-(f[i]*(f[i]-1) div 2);
  end;

  top:=0;
  for i:=1 to tail do
  begin
    writeln(top+1,' ',top+b[i]);
    for j:=top+2 to top+b[i] do writeln(j-1,' ',j);
    top:=top+b[i];
  end;
  for i:=top+1 to n do
    if i<>1 then writeln(i,' ',1);
end.

Program Network;
 Const Max=100; Mr=Max*Max Div 2;
 Var i,j,n,k,p,v,st:Longint;
     a,b:Array[0..Mr] Of Longint;
Begin
 a[0]:=0; b[0]:=0;
 For i:=1 To Mr Do Begin
  a[i]:=Max+1;
  For j:=3 To Max Do Begin
   v:=i-j*(j-1) Div 2;
   If v>=0 Then
    If a[v]+j<=a[i] Then Begin
     a[i]:=a[v]+j;
     b[i]:=j;
    End;
  End;
 End;
 Readln(n,k);
 k:=n*(n-1) Div 2 - k;
 If a[k]>n Then
  Writeln(-1)
 Else Begin
  p:=1;
  v:=k;
  While v>0 Do Begin
   st:=p;
   If st<>1 Then
    Writeln('1 ',st);
   For i:=1 To b[v]-1 Do Begin
    Writeln(p,' ',p+1);
    Inc(p);
   End;
   Writeln(p,' ',st);
   Inc(p);
   Dec(v,b[v]*(b[v]-1) Div 2);
  End;
  While p<=n Do Begin
   If p<>1 Then
    Writeln('1 ',p);
   Inc(p);
  End;
 End;
End.

Here is my new program:

Program Network;
 Const Max=100; Mr=Max*Max Div 2;
 Var i,j,n,k,p,v,st:Longint;
     a,b:Array[0..Mr] Of Longint;
Begin
 a[0]:=0; b[0]:=0;
 For i:=1 To Mr Do Begin
  a[i]:=Max+1;
  For j:=3 To Max Do Begin
   v:=i-j*(j-1) Div 2;
   If v>=0 Then
    If a[v]+j<=a[i] Then Begin
     a[i]:=a[v]+j;
     b[i]:=j;
    End;
  End;
 End;
 Readln(n,k);
 k:=n*(n-1) Div 2 - k;
 If a[k]>n Then
  Writeln(-1)
 Else Begin
  p:=1;
  v:=k;
  While v>0 Do Begin
   st:=p;
   If st<>1 Then
    Writeln('1 ',st);
   For i:=1 To b[v]-1 Do Begin
    Writeln(p,' ',p+1);
    Inc(p);
   End;
   Writeln(p,' ',st);
   Inc(p);
   Dec(v,b[v]*(b[v]-1) Div 2);
  End;
  While p<=n Do Begin
   Writeln('1 ',p);
   Inc(p);
  End;
 End;
End.

Here is my program. Could anyone at least give me some test data so
my program would give incorrect answers?

Program Network;
 Const Max=100; Mr=Max*Max Div 2;
 Var i,j,n,k,p,v:Longint;
     a,b:Array[0..Mr] Of Longint;
Begin
 a[0]:=0; b[0]:=0;
 For i:=1 To Mr Do Begin
  a[i]:=Max+1;
  For j:=3 To Max Do Begin
   v:=i-j*(j-1) Div 2;
   If v>=0 Then
    If a[v]+j<=a[i] Then Begin
     a[i]:=a[v]+j;
     b[i]:=j;
    End;
  End;
 End;
 Readln(n,k);
 k:=n*(n-1) Div 2 - k;
 If a[k]>n Then
  Writeln(-1)
 Else Begin
  p:=2;
  v:=k;
  While v>0 Do Begin
   Writeln('1 ',p);
   For i:=1 To b[v]-2 Do Begin
    Writeln(p,' ',p+1);
    Inc(p);
   End;
   Writeln(p,' 1');
   Inc(p);
   Dec(v,b[v]*(b[v]-1) Div 2);
  End;
  While p<=n Do Begin
   Writeln('1 ',p);
   Inc(p);
  End;
 End;
End.

Is it possible for a pair of computers to be linked directly by more
than one connection?

e.g. for input
3 2

Is the following an acceptable output?

1 2
2 3
2 3

Or is the output -1 ?

Thanks.