{ J.Blonskis. Naudojama gretutinumo matrica }
program VirusasA;
const Cn = 50;           { Maksimalus virðûniø skaièius}
type  Mas = array[1..Cn] of boolean;
      Mtr = array[1..Cn] of Mas;
const  CD = 'virus.dat';   {Duomenø failo vardas  }
       CR = 'virus.re';        {Rezultatø failo vardas}
var   K : Mtr; n  : integer;  {Gretutinumo matrica   }
      F1, F2, Kv  : Mas;      {Frontø registracija ir virðûniø sàraðas}
      A, B, t     : integer;  {Starto ir tikslo virðûnës, laikas}
      R : text;
{--------------------------------------------------}
procedure Valo( var A : Mas); {Masyvà uþpildo loginiu nuliu}
var i : integer;
begin
  for i := 1 to n do A[i] := False;
end;
{--------------------------------------------------}
procedure Duomenys;             {Duomenø skaitymas }
var i, j : integer;  F : text;
    sim  : char;     v, v1, m : integer;
begin
 for i := 1 to n do Valo(K[i]);   {Valoma matrica}
 Valo(F1);  Valo(F2);  Valo( Kv); {Valomi frontai ir virðûniø sàraðas}
 Assign(F, CD);  Reset(F);
 ReadLn(F, n, A, B);              {Virðûniø skaièius, starto ir tikslo virðûnës}
 for i := 1 to n do  begin
   Read(F, sim, v, m);            {Virðûnës tipas, numeris ir ryðiø skaièius   }
   if sim = 'T' then Kv[v] := True; {Virðûnës tipas paþymimas sàraðe }
    for j := 1 to m do begin      {Skaitomi ryðiai}
      Read(F, v1);                {Ryðio virðûnë  }
      K[v, v1] := True;   K[v1, v] := True; {Ryðio tarp virðûniø atþyma matricoje}
    end;
      ReadLn(F);                  {Perëjimas á naujà eilutæ }
 end;
 Close(F);
end;
{--------------------------------------------------}
function ArYra: boolean;
begin
  ArYra := F2[B];   {Tikrinama, ar tikslas pasiektas}
end;
{--------------------------------------------------}
function ArTuscias: boolean;
var yra : boolean;  i : integer;
begin        {Tikrinama, ar dar yra kelias nors á vienà virðûnæ}
    yra := False;  i := 1;
    while not yra and (i <= n) do
      if F2[i]  then yra := True
                else i := i +1;
    ArTuscias := yra;
end;
{--------------------------------------------------}
procedure Zingsnis;         {Vienas viruso þingsnis}
var i, j : integer;
begin
  for i := 1 to n do        {Senojo fronto sàraðo perþiûra}
    if F1[i] then           {Virusas startuoja            }
      for j := 1 to n do    {Ryðiø perþiûra               }
         if K[i,j] then begin {Nauja virðûnë: atþyma naujame fronte; ðalinamas ryðys}
               F2[j] := True;  K[i,j] := False;  K[j,i] := False;
                        end;
  for i := 1 to n do  {Ið naujo fronto ðalinamos virðûnës, turinèios antivirusinæ apsaugà}
     if F2[i] and Kv[i] and not F2[B] then
        begin Kv[i] := False; F2[i] := False; end;
end;
{--------------------------------------------------}
procedure F2Tvarko; {Koreguojamas naujo fronto virðûniø sàraðas }
var i, j : integer; yra : boolean;
begin			{Jeigu ið F1[i] virðûnës tolesniø ryðiø nëra, tai ji
                         paðalinama ið fronto sàraðo            }
   for i := 1 to n do
      if F2[i] then begin
         yra := False;  j := 1;
         while not yra and (j <= n)  do
           if K[i,j] then yra := True
                     else j := j + 1;
         if not yra and not F2[B] then F2[i] := False;
      end;
end;
{--------------------------------------------------}
procedure Darbas; {Viruso plitimo organizavimas    }
begin
  F2[A] := True;  {Startas}
  t := 0;         {Laikas }
  while not ArYra and ArTuscias do begin {Tikslas nepasiektas, bet dar paieðka galima}
    t := t + 1;           {Dar vienas þingsnis   }
    F1 := F2;  Valo(F2);  {Fronto pakeitimas     }
    Zingsnis;             {Vienas viruso þingsnis}
    F2Tvarko;             {Naujo fronto sàraðo korekcija}
    end;
end;
{--------------------------------------------------}
begin
  Assign(R, CR);  Rewrite(R);
  Duomenys;
  Darbas;
  if ArYra then Write(R, 'T ', t)
           else Write(R, 'N ', t);
  Close(R);
end.
