Форум Всеукраїнської інтернет-олімпіади NetOI

program FERRYisBACK;
const maxpol=10000;
type pol=array[1..maxpol] of    record 
                                                                p:integer;
                                                                u:boolean;
                                                            end;    
         spnter=^sso;
         sso=record
                      x:integer;
                     p:spnter;
                 end;    
         ssor=array[1..maxpol] of spnter; 
         group=array[0..maxpol-1] of integer;

var pp:pol;
        ss:ssor;
        e,f:group;
        n:integer;

procedure rss(q:integer;var s:ssor);
var i,m,k,j:integer;
        a,prev:spnter;
begin
    read(m);
    for i:=1 to maxpol do
    s[i]:=nil;
    for k:=1 to m do
    begin 
        read(i,j);
        a:=s[i];
        prev:=nil;
        while a<>nil do 
        begin
            prev:=a;
            a:=a^.p;
        end;    
        new(a);
        a^.x:=j;
        if prev=nil then
        begin
        new(s[i]);
        s[i]^.p:=a;
        end
        else
        prev^.p:=a;
        a:=s[j];
        prev:=nil;
        while a<>nil do 
        begin
            prev:=a;
            a:=a^.p;
        end;    
        new(a);
        a^.x:=i;
        if prev=nil then
        begin
            new(s[j]);
            s[j]^.p:=a;
        end
        else    
        prev^.p:=a;
    end;    
end;

function findf(a,q:integer;p:pol):integer;
var i:integer;
begin
    i:=1;
    while ((p[i].u)or(p[i].p<>a))and(i<=q) do inc(i);
    if i=q+1 then
    begin
    i:=1;
    while (p[i].u)and(p[i].p<>0) do inc(i);
    end;
    findf:=i;
end;

function allus(q:integer;p:pol):boolean;
var i:integer;
begin
    i:=1;
    while p[i].u do inc(i);
    allus:=i>q;
end;

function is(i,j:integer;s:ssor):boolean;
var a:spnter;
begin
a:=s[i];
while (a<>nil) and (a^.x<>j) do
begin
    a:=a^.p;
end;    
is:=a<>nil;
end;

function polarn(s:ssor;q:integer;var p:pol):integer;
var i,l,last:integer;
begin
    p[1].p:=1;
    p[1].u:=true;
    for i:=2 to q do
        if is(1,i,s) then
            p[i].p:=-1;
    last:=1;
    while not allus(q,p) do
        begin
            l:=findf(0-last,q,p);
            if p[l].p=0 then p[l].p:=1;
            p[l].u:=true;
            for i:=1 to q do
                if is(i,l,s) then
                    if p[i].p<>p[l].p then
                    begin
                        p[i].p:=0-p[l].p
                    end
                    else
                    begin
                        polarn:=0;
                        exit;
                    end;
            last:=0-last;
        end;
    polarn:=1;
end;    

procedure grouping(a:pol;q:integer;var b,c:group);
var k,l,i:integer;
begin
k:=1;l:=1;
for i:=1 to q do
    if a[i].p=1 then
        begin
            b[k]:=i;
            inc(k);
        end
    else
        begin
            c[l]:=i;
            inc(l);
        end;
b[0]:=k-1;
c[0]:=l-1;
if b[0]=0 then 
begin
    b[0]:=1;
    b[1]:=c[c[0]];
    dec(c[0]);
end;    
if c[0]=0 then 
begin
    c[0]:=1;
    c[1]:=b[b[0]];
    dec(b[0]);
end;    
end;

procedure wrgr(b,c:group);
var i:integer;
begin
    for i:=1 to b[0] do
        write(b[i],' ');
    writeln;
    for i:=1 to c[0] do
        write(c[i],' ');
    writeln;
end;

begin
read(n);
rss(n,ss);
if polarn(ss,n,pp)=1 then
begin
    grouping(pp,n,e,f);
    writeln('1');
    wrgr(e,f);
end
else
writeln('0');
end.