{
TASK: move
LANG:PASCAL
}

type
 tn = 1..100 {10}; {v}
 tm = 1..1000 {100}; {r}
 tp = tn;    {p}
 tl = 0..100{tn};    {l}

type
 x = array[tn] of tp;

var
 n, j, k : tn;
 m, i : tm;
 ra, rb : array[tm] of tn;
 p : x;
 b : boolean;
 a : array[tn, tn] of tl;
 s : word {tl};
 kk : tn;

function find(p : x; k : tn): LongInt;
var r, r1 : LongInt;
 i : tm;
 pp : x;
Begin
 r := maxlongint;

 for i := 1 to m do
 Begin
  if ra[i]=k then
  Begin
   pp := p;

   pp[k] := rb[i];
   pp[rb[i]] := k;

   r1 := find(pp, rb[i]);
   if r1 < r then r := r1;
  end;

  if rb[i]=1 then
  Begin
   pp := p;

   pp[1] := ra[i];
   pp[ra[i]] := 1;

   r1 := find(pp, rb[i]);
   if r1 < r then r := r1;
  end;
 end;

 find := r;
end;

Begin
 readln(n, m);
 for i := 1 to m do readln(ra[i], rb[i]);
 for j := 1 to n do Begin read(p[j]); if p[j]=1 then kk := j; end;

 for j := 1 to n do
  for k := 1 to n do
   byte(a[j, k]) := 101;

 writeln(find(p, kk));
end.