Main.java

import java.io.*;
import java.util.*;

class Main {
  
  public static void main(String[] args) throws IOException {
    
    startDay27();
  
  }

  

  public static void startDay27() {
    
    FastReader sc = new FastReader();

    

    int n = sc.nextInt();
    
    int m = sc.nextInt();

    

    long[][] c = new long[n + 1][n + 1];

    

    HashMap<Integer, List<Integer>> graph = new HashMap<>();

    

    for (int i = 0; i < m; i++) {

      

      int a = sc.nextInt();
      
      int b = sc.nextInt();

      

      graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
      
      graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a);

      

      c[a][b] = 1L;
      
      c[b][a] = 1L;

    

    }

    

    sourceInf ed = new sourceInf(graph, c, 1, n, n + 1);
    
    long f = ed.maxflow();

    

    System.out.println(f);

    

    boolean[] v = new boolean[n + 1];
    
    Arrays.fill(v, false);
    
    dfs(1, graph, c, n, v);

    

    for (int i = 1; i <= n; i++) {
      
      for (int j = 1; j <= n; j++) {
        
        if (i == j)
          
          continue;
        
        if (((v[i] && !v[j]) || (v[j] && !v[i])) && c[i][j] > 0)
          
          System.out.println(i + " " + j);
      
      }
    
    }
  
  }

  

  private static void dfs(int u, HashMap<Integer, List<Integer>> graph, long[][] c, int t, boolean[] vs) {
    
    vs[u] = true;
    
    if (!graph.containsKey(u))
      
      return;
    
    for (int v : graph.get(u)) {
      
      if (v != t && !vs[v] && c[u][v] > 0)
        
        dfs(v, graph, c, t, vs);
    
    }

  

  }

  

  static class sourceInf {

    

    HashMap<Integer, List<Integer>> g;
    
    long[][] c;
    
    int s;
    
    int t;
    
    int n;

    

    long INF = Long.MAX_VALUE;

    

    //  source, target, totalnodes except source & target
    
    public sourceInf(HashMap<Integer, List<Integer>> g, long[][] c, int s, int t, int n) {
      
      this.g = g;
      
      this.c = c;
      
      this.s = s;
      
      this.t = t;
      
      this.n = n;
    
    }

    

    private long bfs(int[] parent) {
      
      Arrays.fill(parent, -1);

      

      LinkedList<long[]> q = new LinkedList<>();
      
      q.add(new long[]  {  s, INF  });

      

      parent[s] = -2;

      

      while (q.size() > 0) {
        
        long[] node = q.remove();
        
        int u = (int) node[0];
        
        long flow = node[1];

        

        if (!g.containsKey(u))
          
          continue;
        
        for (int v : g.get(u)) {
          
          if (parent[v] == -1 && c[u][v] > 0) {
            
            parent[v] = u;
            
            long newFlow = Math.min(flow, c[u][v]);
            
            if (v == t)
              
              return newFlow;

            

            q.add(new long[]  {  v, newFlow  });
          
          }
        
        }
      
      }
      
      return 0;

    

    }

    

    public long maxflow() {

      

      long ans = 0;

      

      int[] parent = new int[n];
      
      long flow = bfs(parent);
      
      while (flow != 0) {
        
        ans += flow;
        
        int curr = t;
        
        int prev = t;
        
        while (curr != s) {
          
          prev = parent[curr]; //  2
          
          c[prev][curr] -= flow;
          
          c[curr][prev] += flow;
          
          curr = prev;
        
        }
        
        flow = bfs(parent);
      
      }

      

      return ans;
    
    }
  
  }

  

  static class FastReader {
    
    BufferedReader br;
    
    StringTokenizer st;

    

    public FastReader() {
      
      br = new BufferedReader(new InputStreamReader(System.in));
    
    }

    

    String next() {
      
      while (st == null || !st.hasMoreElements()) {
        
        try {
          
          st = new StringTokenizer(br.readLine());
        
        } catch (IOException e) {
          
          e.printStackTrace();
        
        }
      
      }
      
      return st.nextToken();
    
    }

    

    int nextInt() {
      
      return Integer.parseInt(next());
    
    }
  
  }
}