program project1;

{$mode objfpc}{$H+}
type
  Neighbor = record
    S, F: integer;
  end;

var
  i, j, m, n, w1, w2, numStay, numAdd: Integer;
  Chip: array of array of Boolean;
  Visited: array of Boolean;
  NeedAdd: array of Integer;
  StayChip: array of Neighbor;

procedure dfs(v: integer);
var
  i: integer;
begin
  Visited[v] := True;
  for i := 0 to High(Visited) do
    if Chip[v][i] and not Visited[i] then begin
      StayChip[numStay].S := v;
      StayChip[numStay].F := i;
      Inc(numStay);
      dfs(i);
    end;
end;

begin
  Assign(input, 'input.txt'); Reset(input);
  Assign(output, 'output.txt'); Rewrite(output);
  Read(n, m);
  SetLength(Chip,  n, n);
  SetLength(Visited, n);
  SetLength(StayChip, n);
  for i := 1 to m do begin
    Read(w1, w2);
    Chip[w1-1][w2-1] := true;
    Chip[w2-1][w1-1] := true;
  end;
  dfs(0);
  for i := 1 to High(Visited) do
    if not Visited[i] then begin
        dfs(i);
      Inc(numAdd);
      SetLength(NeedAdd, Length(NeedAdd) + 1);
      NeedAdd[High(NeedAdd)] := i+1;
    end;
  WriteLn(numStay);
  for i := 0 to High(StayChip) do
    if StayChip[i].S <> StayChip[i].F then
      WriteLn(StayChip[i].S+1, ' ', StayChip[i].F+1)
    else Break;

  WriteLn(numAdd);
  for i := 0 to High(NeedAdd) do
    WriteLn(NeedAdd[i], ' ', 1);



  Close(input);
  Close(output);
end.