program BehMestem;
const MAXN = 512;

type Uk = ^tUzel;
     tUzel = record
       info : integer;
       dalsi : Uk;
     end;
  
     tVrchol = record
       navstiven : boolean;
       naslednici : Uk;
       stupen : integer;
     end;

var FIFO : array [0..MAXN] of integer;
    zac,kon : integer;
    vrchol : array [1..MAXN] of tVrchol;
    v1,v2,i,j,x,N,M,cil : integer;
    P : Uk;

begin
  readln(N,M,cil);
  
  for x:=1 to N do begin
    vrchol[x].naslednici:=nil;
    vrchol[x].stupen:=0;
    vrchol[x].navstiven:=false;
  end;

  for x:=1 to M do begin
    readln(i,j);
    
    new(P);                       { vytváření seznamu následníků }
    P^.info:=i;
    P^.dalsi:=vrchol[j].naslednici;
    vrchol[j].naslednici:=P;
    
    new(P);
    P^.info:=j;
    P^.dalsi:=vrchol[i].naslednici;
    vrchol[i].naslednici:=P;
  end;

  FIFO[0]:=cil;                   { začínáme od cíle }
  zac:=0;
  kon:=1;

  while zac<kon do begin          { dokud je co zpracovávat }
    v1:=FIFO[zac];
    inc(zac);
    
    vrchol[v1].navstiven:=true;
    
    P:=vrchol[v1].naslednici;
    while P<>nil do begin          { projdeme všechny sousedy }
      v2:=P^.info;
      P:=P^.dalsi;
      
      if not vrchol[v2].navstiven then begin
        FIFO[kon]:=v2;
        inc(kon);
        writeln(v2,' -> ',v1);    { nově zorientované hrany vypisujeme }
      end;
    end;
  end;
end.