URAL/1096

来自"NOCOW"

//program cao 纪念我们伟大的曹师傅

 #include <stdio.h>
 long k,r,a,b;
 long edge[1010][2];
 long path[1010];
 long dis[1010];
 void Init()
 {
      long i,x,y;
      scanf("%ld",&k);
      for(i=1;i<=k;i++)
      {
         scanf("%ld%ld",&x,&y);
         edge[i][0]=x;
         edge[i][1]=y;
      }
      scanf("%ld%ld%ld",&r,&a,&b);
 }
 void PrintCan(long x)
 {
      long y;
      y=edge[x][0];
      printf("%ld\n",dis[y]);
      do
      {
         printf("%ld\n",path[y]);
         y=edge[path[y]][1];
      }while(y!=r);
      exit(0);
 }
 void PrintImp()
 {
      printf("IMPOSSIBLE\n");
 }  
 void BFS()
 {
      long i,x,y;
      short flag;
      for(i=1;i<=1000;i++) dis[i]=20000000;
      dis[r]=0;
      do
      {
         flag=0;
         for(i=1;i<=k;i++)
         {
            x=edge[i][0];
            y=edge[i][1];
            if((dis[y]<20000000)&&(dis[x]==20000000))
            {
               dis[x]=dis[y]+1;
               path[x]=i;
               if((x==a)||(x==b)) PrintCan(i);
               flag=1;
            }
         }
      }while(flag);
      PrintImp();
 }
 int main()
 {
     Init();
     BFS();
     return 0;
 }

const
  maxk=1000+5;
var
  k,i,j,goal,head,tail,now,last:longint;
  a,b:array[1..maxk] of longint;
  go:array[1..maxk,0..maxk] of longint;
  f,path:array[1..maxk] of longint;
  d:array[1..maxk shl 1] of longint;
  v:array[1..maxk] of boolean;
begin
  readln(k);
  for i:=1 to k do
    readln(a[i],b[i]);
  readln(goal,a[i+1],b[i+1]);
  inc(k);
  fillchar(go,sizeof(go),0);
  for i:=1 to k do
    begin
      for j:=1 to i-1 do
        if (a[i]=a[j]) or (b[i]=a[j]) then
          begin
            inc(go[i,0]);
            go[i,go[i,0]]:=j;
          end;
      for j:=i+1 to k do
        if (a[i]=a[j]) or (b[i]=a[j]) then
          begin
            inc(go[i,0]);
            go[i,go[i,0]]:=j;
          end;
    end;
  filldword(f,sizeof(f) div 4,maxlongint);
  filldword(path,sizeof(path) div 4,maxlongint);
  f[k]:=0;
  fillchar(v,sizeof(v),false);v[k]:=true;
  d[1]:=k;
  head:=1;tail:=1;
  while head<=tail do
    begin
      now:=d[head];
      for i:=1 to go[now,0] do
        if f[go[now,i]]>f[now]+1 then
          begin
            f[go[now,i]]:=f[now]+1;path[go[now,i]]:=now;
            if not(v[go[now,i]]) then
              begin
                inc(tail);
                d[tail]:=go[now,i];
                v[go[now,i]]:=true;
              end;
          end;
      v[now]:=false;
      inc(head);
    end;
  j:=maxlongint;last:=0;
  for i:=1 to k do
    if (a[i]=goal) or (b[i]=goal) then
      if f[i]<j then
        begin
          j:=f[i];
          last:=i;
        end;
  if last=0 then
    begin
      writeln('IMPOSSIBLE');
      halt;
    end;
  i:=1;j:=last;
  d[1]:=last;
  while path[j]<>k do
    begin
      inc(i);
      d[i]:=path[j];
      j:=path[j];
    end;
  writeln(i);
  for j:=i downto 1 do
    writeln(d[j]);
end.