{$APPTYPE CONSOLE}
{$Q+,R+}

uses
  SysUtils;

const
  N_MAX = 100000;
  T_MAX = 1000000;
  SHUFF_MAX = 10000;
  NO_MARKED_UNDER_1 = 'nmu1';
  LCA_IS_NOT_ROOT = 'linr';
  START_ATTEMPTS = 3; // for mode LCA_IS_NOT_ROOT

var
  n,k,i,x,cnt,r,m,start,subroot:integer;
  mode:string;
  ts,vt,p,t,new_num,new_pos,d:array[1..N_MAX] of integer; // _num for new, _pos - for old
  ut:array[0..T_MAX] of boolean;
  b,e,pr:array[1..N_MAX] of integer;
  l:array[1..N_MAX] of integer;
  u:array[1..N_MAX] of boolean;
  marked:array[1..N_MAX] of boolean;

procedure swap(var a,b:integer);
var c:integer;
begin
  c:=a;
  a:=b;
  b:=c;
end;

procedure shuffle(l,r:integer);
var i,a,b:integer;
begin
  if l>r then exit;
  for i:=1 to SHUFF_MAX do
  begin
    a:=random(r-l+1)+l;
    b:=random(r-l+1)+l;
    swap(new_num[a],new_num[b]);
  end;
end;

procedure dfs(v,depth:integer);
var r:integer;
begin
  u[v]:=true;
  d[v]:=depth;
  r:=l[v];
  while r<>0 do
  begin
    dfs(e[r],depth+1);
    r:=pr[r];
  end;
end;

begin
  if paramcount<4 then
  begin
    writeln('Too few params');
    halt;
  end;
  randseed:=strtoint(paramstr(1));
  n:=strtoint(paramstr(2));
  k:=strtoint(paramstr(3));
  mode:=paramstr(4);

  p[1]:=0;
  m:=0;
  fillchar(l,sizeof(l),0);
  for i:=2 to n do
  begin
    p[i]:=random(i-1)+1;
    inc(m);
    b[m]:=p[i];
    e[m]:=i;
    pr[m]:=l[b[m]];
    l[b[m]]:=m;
  end;
  fillchar(ut,sizeof(ut),0);
  ut[0]:=true;
  for i:=2 to n do
  begin
    repeat
      x:=random(T_MAX+1);
    until not ut[x];
    ut[x]:=true;
  end;
  cnt:=0;
  for i:=0 to T_MAX do
  if ut[i] then
  begin
    inc(cnt);
    ts[cnt]:=i;
  end;  // Now ts is sorted array of all values of t[i] (all t[i]s are different!)

  cnt:=1;
  vt[1]:=1;
  i:=1;
  while cnt>0 do
  begin
    x:=random(cnt)+1;
    swap(vt[x],vt[cnt]);
    t[vt[cnt]]:=ts[i];
    dec(cnt);
    r:=l[vt[cnt+1]];
    while r<>0 do
    begin
      inc(cnt);
      vt[cnt]:=e[r];
      r:=pr[r];
    end;
    inc(i);
  end;    // Now we know p[i] and t[i], but vertexes are top. sorted
          // and we need to choose start and marked vertexes
  start:=random(n)+1;
  for i:=1 to k do
  begin
    repeat
      x:=random(n)+1;
    until (not marked[x]) and (x<>start);
    marked[x]:=true;
  end;

  if (mode = LCA_IS_NOT_ROOT) then
  begin
    fillchar(u,sizeof(u),0);
    dfs(1,0);
    for i:=1 to START_ATTEMPTS-1 do
    begin
      x:=random(n)+1;
      if d[x]>d[start] then start:=x;
    end;
    marked[start]:=false; // We have new (deep) start. Need to chose subroot
    subroot:=start;
    for i:=1 to (d[start] div 2) do subroot:=p[subroot];
    // Now we need to keep marked only vertexes under subroot
    fillchar(u,sizeof(u),0);
    dfs(subroot,-1);
    k:=0;
    for i:=1 to n do
    begin
      marked[i]:=marked[i] and u[i];
      k:=k+ord(marked[i]);
    end;
  end;

  if (mode = NO_MARKED_UNDER_1) then
  begin
    fillchar(u,sizeof(u),0);
    dfs(start,-1);
    k:=0;
    for i:=1 to n do
    begin
      marked[i]:=marked[i] and (not u[i]);
      k:=k+ord(marked[i]);
    end;
  end;

  cnt:=1;              // shuffling
  new_num[1]:=start;
  for i:=1 to n do
  if marked[i] and (i<>start) then
  begin
    inc(cnt);
    new_num[cnt]:=i;
  end;
  shuffle(2,k+1);
  for i:=1 to n do
  if (not marked[i]) and (i<>start) then
  begin
    inc(cnt);
    new_num[cnt]:=i;
  end;
  shuffle(k+2,n);
  for i:=1 to n do new_pos[new_num[i]]:=i;

  start:=new_pos[start];
  for i:=1 to n do
    if p[i]<>0 then p[i]:=new_pos[p[i]];


  writeln(n,' ',k);
  for i:=1 to n do writeln(p[new_num[i]],' ',t[new_num[i]]);
end.