I used greedy algo, pascal, 0.265sec works, O(2*M*K) too.

10 2 5 1
1 6
1 4
4 5
5 8
7 9

Answer:
5
1 2 3 4 5
May be test 7 is another thing.I don't know exactly.

Edited by author 16.05.2009 11:57

Try this one:
10 3 5 1
1 2
1 5
1 7
6 8
4 9

The answer is:
5
1 2 3 4 5

Probably you should try to find a bug in your code. It doesn't look like this problem have any troubles with test data.

I have WA9 too.
try test:
3 1 2 1
1 3
1 2

Try this:
10 2 4 1
1 4
1 1
4 5
3 6

The answer is:
4
1 2 3 4

    Up to now.I can't find what's wrong with my program?
    I use greedy algorithm with heap.
    Here is my code:
    program mini;
const
  maxn=201000;
var
  h,p,l,list:array [0..maxn] of longint;
  vis:array [0..maxn] of boolean;
  g,next,v,d,g1,next1,v1:array [0..maxn] of longint;
  i,j,k,m,n,r,q,e,t:longint;
  ans:qword;
procedure insert(u:longint);
  begin
    inc(e);next[e]:=g[u];g[u]:=e;v[e]:=r;d[e]:=j;
  end;
procedure ins(u:longint);
  begin
    next1[r]:=g1[u];g1[u]:=r;v1[r]:=r;
  end;
procedure swap(var x,y:longint);
  var t:longint;
  begin
    t:=x;x:=y;y:=t;
  end;
procedure up(k:longint);
  begin
    while (k>1) and (h[k shr 1]<h[k]) do
      begin
        swap(h[k shr 1],h[k]);
        swap(l[k shr 1],l[k]);
        p[l[k shr 1]]:=k shr 1;p[l[k]]:=k;
        k:=k shr 1;
      end;
  end;
procedure down(k:longint);
  begin
    repeat
     j:=k;
     if (j shl 1<=t) and (h[j shl 1]>h[k]) then k:=j shl 1;
     if (j shl 1+1<=t) and (h[j shl 1+1]>h[k]) then k:=j shl 1+1;
     if j<>k
       then begin
              swap(h[j],h[k]);
              swap(l[j],l[k]);
              p[l[j]]:=j;p[l[k]]:=k;
            end;
    until j=k;
  end;
procedure init;
  begin
    read(n,m,k,q);
    for r:=1 to k do
      begin
        read(i,j);if i=j then repeat until false;
        if i>j then swap(i,j);
        insert(i);
        ins(j);
      end;
  end;
procedure solve;
  begin
    ans:=0;t:=0;
    for i:=1 to n do
      begin
        r:=g1[i];
        while r<>0 do
          begin
            if vis[v1[r]]
              then begin
                     inc(ans);list[ans]:=v1[r];
                     inc(m);vis[v1[r]]:=false;
                     h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t);
                     down(p[v1[r]]);
                   end;
            r:=next1[r];
          end;
        r:=g[i];
        while r<>0 do
          begin
            dec(m);vis[v[r]]:=true;
            inc(t);l[t]:=v[r];p[v[r]]:=t;h[t]:=d[r];
            up(t);
            r:=next[r];
          end;
        while m<0 do
          begin
            vis[l[1]]:=false;h[1]:=h[t];l[1]:=l[t];p[l[1]]:=1;dec(t);
            down(1);
            inc(m);
          end;
        r:=g1[i];
        while r<>0 do
          begin
            if vis[v1[r]]
              then begin
                     inc(ans);list[ans]:=v1[r];
                     inc(m);vis[v1[r]]:=false;
                     h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t);
                     down(p[v1[r]]);
                   end;
            r:=next1[r];
          end;
      end;
  end;
procedure print;
  begin
    writeln(ans*q);
    if ans=0 then exit;
    for i:=1 to ans-1 do write(list[i],' ');writeln(list[ans]);
  end;
begin
  assign(input,'mini.in');reset(input);
  assign(output,'mini.out');rewrite(output);
  init;
  solve;
  print;
  close(input);close(output);
end.

   Could you tell me what's wrong with my program?Or let me refer to your AC program?
   Thanks.

You Algo is Wrong for 100 percent. First i solved as you now i AC

PLZ HELP