i use 0(n^2) algo, but i got TlE.
here is my code

-----------------------------------------------

program The_Prufer_Code;
   const maxn=7500;
   var n:integer;
       a:array[1..maxn]of integer;
       num:array[1..maxn]of integer;
       link:array[1..maxn,1..2]of integer;
       mark:array[1..maxn]of integer;
       ans:array[1..maxn]of boolean;
       total:integer;



   procedure init;
      var i:integer;
    begin
      fillchar(num,sizeof(num),0);
      fillchar(a,sizeof(a),0);
      n:=0;
      while not eof do begin
        inc(n);
        read(a[n]);
        inc(num[a[n]]);
      end;
      inc(n);
    end;



   procedure work;
      var i,j:integer;
    begin
      fillchar(link,sizeof(link),0);
      total:=0;
      for i:=1 to n-1 do begin
        for j:=1 to n-1 do if num[j]=0 then begin
          inc(total);
          link[total,1]:=a[i];
          link[total,2]:=j;
          dec(num[j]);
          break;
        end;
        dec(num[a[i]]);
      end;
    end;



   procedure print;
      var i,j,k:integer;
    begin
      fillchar(mark,sizeof(mark),0);
      for i:=1 to n do begin
        write(i,':');
        fillchar(ans,sizeof(ans),0);
        for j:=1 to total do if mark[j]<2 then begin
          for k:=1 to 2 do
            if link[j,k]=i then begin
              ans[link[j,3-k]]:=true;
              inc(mark[j]);
              break;
            end;
        end;
        for j:=1 to n do
          if ans[j] then write(' ',j);
        writeln;
      end;
    end;



begin
  Init;
  Work;
  Print;
end.

If you encourage problems I can post my code.

> If you encourage problems I can post my code.

Please someone can post his AC because for 6 months i can't take AC
with a correct source (i'm sure of it...)