{$define DEBUG}

{$define REDIRECT}

{$ifdef VER70}
const MAXN= 5000;
      MAXM=10000;
{$else}
const MAXN=10000;
      MAXM=20000;
{$endif}

const MY_NAN=-1;

type PList__=^TList__;
     TList__ = record
               v:integer;
               next:PList__;
             end;
     TList = object
               head:PList__;
               constructor Create;
               procedure AddHead(v:integer);
               function isEmpty:boolean;
               function ExtractHead(var v:integer):boolean;
             end;

constructor TList.Create;
Begin
  head:=nil;
End;

procedure TList.AddHead(v:integer);
var p:PList__;
Begin
  new(p);
  p^.v:=v;
  p^.next:=head;
  head:=p;
End;

function TList.isEmpty:boolean;
Begin
  isEmpty:=head=nil;
End;

function TList.ExtractHead(var v:integer):boolean;
var p:PList__;
Begin
  if head=nil then begin
    v:=MY_NAN;
    ExtractHead:=false;
    exit
  end;
  p:=head^.next;
  v:=head^.v;
  dispose(head);
  head:=p;
End;

var which_part:array[1..MAXN] of {$ifdef DEBUG}integer{$else}shortint{$endif};
    gr:array[1..MAXN] of TList;
    THE_N,THE_M:integer;
    v1,v2:integer;
    var Q:array[0..1] of TList;

procedure ReadData;
var i:integer;
Begin
  read(THE_N);
  for i:=1 to THE_N do begin
    gr[i].Create;
    which_part[i]:=MY_NAN;
  end;
  read(THE_M);
  for i:=1 to THE_M do begin
    read(v1,v2);
    gr[v1].AddHead(v2);
    gr[v2].AddHead(v1);
  end;
End;

procedure OutputGoodRes;
var i:integer;
Begin
  writeln('1');
  for i:=1 to THE_N do
    if which_part[i]=0 then
      write(i,' ');
  writeln;
  for i:=1 to THE_N do
    if which_part[i]=1 then
      write(i,' ');
  writeln;
End;

procedure OutputBadRes;
Begin
  writeln('0');
End;

function SearchInComponent(v_start:integer):boolean;
var step:integer;
    v,u:integer;
Begin
  step:=v_start mod 2;
  which_part[v_start]:=step;
  Q[step].AddHead(v_start);
  repeat
    while Q[step].ExtractHead(v) do begin
      while gr[v].ExtractHead(u) do begin
        if which_part[u]=MY_NAN then begin
          which_part[u]:=1-step;
          Q[1-step].AddHead(u);
        end else
          if which_part[u] = which_part[v] then begin
            SearchInComponent:=false;
            exit;
          end;
      end;
    end;
    step:=1-step;
  until Q[step].isEmpty;
  SearchInComponent:=true;
End;

function ApplySearch:boolean;
var v_start:integer;
Begin
  Q[0].Create;
  Q[1].Create;
  for v_start:=1 to THE_N do
    if which_part[v_start]=MY_NAN then
      if not SearchInComponent(v_start) then begin
        ApplySearch:=false; exit
      end;
  ApplySearch:=true
End;

var original_heap_state:pointer;

BEGIN
{$ifdef REDIRECT}
  assign(input,'polar2.dat'); reset(input);
{$endif}
  Mark(original_heap_state);
  ReadData;
  if ApplySearch then
    OutputGoodRes
  else
    OutputBadRes;
  release(original_heap_state);
{$ifdef REDIRECT}
  close(input);
{$endif}
END.
