#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int N=200010;
int w[2];
vector <int> v[N];
int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N];
bool f[N];
queue<int> q[N];
void dfs(int x,int y){
    f[x]=1;
    w[y]++;
    col[x] = y;
    ccol[y][sz] = x;
    for (int i=0;i<v[x].size();i++)
    if (!f[v[x][i]])
        dfs(v[x][i],(y^1));
    else if( col[v[x][i]] != 1 - y ) 
        assert(0);
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int k=0;
    for (int i=1;i<=n;i++) {
        if (!f[i]) {
            w[0] = w[1]=0;
            dfs(i,0);
            c[i] = (w[0] < w[1]);
            k+=abs(w[0]-w[1]);
            a[abs(w[0]-w[1])]++;
            q[abs(w[0]-w[1])].push( i );
        }
    }

    for (int j=1;j<=k;j++) d[j]=N;

    for (int i=1;i<=n;i++)
        if (a[i]) {
            for (int j=0;j+i<=k;j++) {
                if( d[i+j] == N && d[j] != N ) {
                    d[i+j] = d[j] + 1;
                    p[i+j] = j;
                }
            }

            for (int j=1;j<=k;j++) {
                if (d[j]>a[i]) {
                    d[j]=N;
                    p[j]=0;
                } else {
                    d[j]=0;
                }
            }
        }

    int ans=k, v = 0;
    for (int i=0;i<=k;i++) {
        if(d[i]<N) {
            if( ans >= abs(k - 2 * i) ) {
                ans = abs(k - 2 * i);
                v = i;
            }
        }
    }

    memset(f, 0, sizeof f);
    while( v != 0 ) {
        int diff = v - p[v];
        int nd = q[diff].front();
        q[diff].pop();
        sz ++;
        dfs(nd, c[nd]);
        v = p[v];
    }

    for(int i=1; i<=n; i++) {
        if( !f[i] ) {
            sz ++;
            dfs(i, 1 - c[i]);
        }
    }

    int blk, wht, idb, idw;
    blk = wht = idb = idw = -1;
    for(int i=1; i<=sz; i++) {

        if( ccol[0][i] ) {
            blk = ccol[0][i];
            idb = i;
        }

        if( ccol[1][i] ) {
            wht = ccol[1][i];
            idw = i;
        }
    }
    cout << ans << " " << sz - 1 << "\n";
    if( idb != idw ) cout << blk << " " << wht << "\n";
    for(int i=1; i<=sz; i++) {
        if( i != idb && i != idw ) {
            if( ccol[0][i] ) {
                cout << wht << " " << ccol[0][i] << "\n";
            } else {
                cout << blk << " " << ccol[1][i] << "\n";
            }
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class BlackAndWhiteTree {
    static final List<Graph> graphs = new ArrayList<>();
    static int ones = 0;
    static int zeroes = 0;

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] line = br.readLine().split(" ");
            Node[] nodes = new Node[Integer.parseInt(line[0])];
            for (int e = 0; e < nodes.length; e++) {
                nodes[e] = new Node(e);
            }
            for (int e = Integer.parseInt(line[1]); e > 0; e--) {
                line = br.readLine().split(" ");
                nodes[Integer.parseInt(line[0]) - 1].adjacent.add(nodes[Integer.parseInt(line[1]) - 1]);
                nodes[Integer.parseInt(line[1]) - 1].adjacent.add(nodes[Integer.parseInt(line[0]) - 1]);
            }
            int components = 0;
            for (int e = 0; e < nodes.length; e++)
                if (!nodes[e].visited) {
                    Graph g = new Graph(nodes[e]);
                    if (g.diffs == 0) {
                        zeroes++;
                    } else if (g.diffs == 1) {
                        ones++;
                    } else {
                        components += g.diffs;
                    }
                    graphs.add(g);
                }

            Collections.sort(graphs, (g1, g2) -> Math.abs(g1.diffs) - Math.abs(g2.diffs));

            final int SIZE = components / 2 + 1;
            boolean[] dinam = new boolean[SIZE];
            int[] parent = new int[SIZE];
            Arrays.fill(parent, Integer.MAX_VALUE);
            dinam[0] = true;
            int lastMax = 0;
            for (int g = ones + zeroes; g < graphs.size(); g++) {
                final int dif = graphs.get(g).diffs, top = Math.min(SIZE, lastMax + dif + 1);
                for (int e = top - 1; e >= dif; e--) {
                    dinam[e] |= dinam[e - dif];
                    if (dinam[e - dif]) {
                        parent[e] = Math.min(parent[e], dif);
                    }
                }
                lastMax += dif;
            }

            int min = 0;
            int mindiff = components;
            for (int e = 0; e < SIZE; e++)
                if (dinam[e] && calcMin(Math.abs(components - 2 * e)) < calcMin(Math.abs(components - 2 * min))) {
                    min = e;
                    mindiff = Math.abs(components - 2 * e);
                }
            final int minValue = calcMin(Math.abs(components - 2 * min));

            for (int g = graphs.size() - 1; g >= 0; g--) {
                if (graphs.get(g).diffs == 0) {
                } else if (graphs.get(g).diffs == 1) {
                    graphs.get(g).signum = g < zeroes + mindiff || (g % 2) == 1;
                } else if (min > 0 && parent[min] == graphs.get(g).diffs) {
                    graphs.get(g).signum = true;
                    min -= graphs.get(g).diffs;
                }
            }

            Collections.sort(graphs, (g1, g2) -> Boolean.compare(g1.signum, g2.signum));

            Graph root = graphs.get(graphs.size() - 1);
            System.out.println(minValue + " " + (graphs.size() - 1));
            for (int g = 0; g < graphs.size() - 1; g++) {
                if (graphs.get(g).signum == root.signum) {
                    root.root.adjacent.get(0).adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root.adjacent.get(0));
                    System.out.println(root.root.adjacent.get(0).id + " " + graphs.get(g).root.id);
                } else {
                    root.root.adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root);
                    System.out.println(root.root.id + " " + graphs.get(g).root.id);
                }
            }
        }
    }

    public static int calcMin(int x) {
        if (ones < x) {
            return x - ones;
        }
        return (ones - x) % 2;
    }

    static class Graph {
        Node root;
        int whites, blacks, diffs, size;
        boolean signum = false;

        public Graph(Node root) {
            this.root = root;
            Stack<Node> n = new Stack<>();
            n.add(root);
            while (!n.isEmpty()) {
                Node next = n.pop();
                if (next.visited)
                    continue;
                next.parent = root.parent;
                next.visited = true;
                if (next.isWhite) {
                    whites++;
                } else {
                    blacks++;
                }
                for (Node e : next.adjacent) {
                    e.isWhite = !next.isWhite;
                    n.push(e);
                }
            }
            diffs = blacks - whites;
            size = blacks + whites;
            if (blacks - whites < 0) {
                invert();
            }
        }

        public void invert() {
            root = root.adjacent.get(0);
            int t = blacks;
            blacks = whites;
            whites = t;
            diffs = blacks - whites;
            size = blacks + whites;
        }
    }

    static class Node {
        int parent, id;
        boolean isWhite, visited;
        ArrayList<Node> adjacent = new ArrayList<>();

        public Node(int parent) {
            this.parent = parent;
            this.id = parent + 1;
        }
    }
}

 

#!/bin/python3

import math
import os
import random
import re
import sys
import itertools

#print(sys.getrecursionlimit())
#sys.setrecursionlimit(30000)

#
# Complete the 'blackWhiteTree' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts UNWEIGHTED_INTEGER_GRAPH g as parameter.
#

#
# For the unweighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] and <name>_to[i].
#
#

# initialise all nodes with one dummy node so that nodes are referenced starting at 1
all_nodes = [-1]
g_edges = 0

def find_smallest_combo(numbers):
    operations = len(numbers)-1
    all_combos = list(itertools.product([0, 1], repeat=operations))
    closest_total = 999999999999
    closest_combo = []

    for combo in all_combos:
        total = int(numbers[0])
        current_combo = []

        #print(total, end="")

        for i in range(operations):
            n = int(numbers[i+1])
            if combo[i] == 1:
                #print('+', end="")
                current_combo.append(True)
                total += n
            else:
                #print('-', end="")
                current_combo.append(False)
                total -= n

        #print(numbers[i], end='')
        #print(f" = {total}")

        if abs(total) < abs(closest_total):
            closest_total = abs(total)
            closest_combo = current_combo
            if closest_total == 0:
                break

    #print(f"closest total is {closest_total}")
    return([closest_total, closest_combo])

class Graph():
    def __init__(self):
        self.true_color = "white" # colour to use if a node is true
        self.node_ids = []
        self.score = 0
    
    def __str__(self):
        return str(self.node_ids)
    
    def flip_colors(self):
        if self.true_color == "white":
            self.true_color = "black"
        else:
            self.true_color = "white"

        self.score = self.score * -1
    
    def get_first_node_id(self):
        for node_id in self.node_ids:
            return node_id
        
    def get_first_node_of_color(self, color):
        for node_id in self.node_ids:
            if all_nodes[node_id].color == color:
                return node_id
            
        # if we can't find a node of this color, return -1
        return -1

    def add_node(self, node):
        self.node_ids.append(node.id)
        if node.color:
            self.score += 1
        else:
            self.score -= 1    
    
    def add_graph(self, new_ids):
        self.node_ids += new_ids
        
        for node_id in new_ids:
            if all_nodes[node_id].color:
                self.score += 1
            else:
                self.score -= 1
    
    def count_colors(self):
        return self.score
        

class Node():
    def __init__(self, id):
        self.id = id
        self.color = True
        self.edges = []
        self.processed = False
    
    def reset(self, to):
        self.color = True
        self.processed = False
        
    def add_edge(self, to):
        self.edges.append(to)
    
    def edges(self):
        return self.edges
    
    def set_color(self, color):        
        self.color = color
    
def build_bipartite_graph(start_id):
    global all_nodes
    
    if all_nodes[start_id].processed:
        return []
    
    #print(f"trying to build bipartite graph starting at node {start_id}")
    graph = [start_id]
    i = 0
    while (i < len(graph)):
        node = all_nodes[graph[i]]
        
        i += 1
        
        #print(f"processing node: {node.id}")
        #print(f"graph is {graph}")
        
        node.processed = True

        other_color = not node.color
        
        for adjacent_node in node.edges:
            #print(f"adjacent_node {adjacent_node.id}")
            if not adjacent_node.processed:
                adjacent_node.processed = True
                #print(f"setting color to {other_color}")
                adjacent_node.set_color(other_color)
                #print(f"adding node {adjacent_node.id} to graph")
                graph.append(adjacent_node.id)
            
    #print(f"returning {graph}")
    return graph

    
def solve():
    start_node = all_nodes[1]
    start_node.set_color(True)
    
    subgraphs = []
    
    #print("subgraph 0 nodes")
    #print(subset_ids)
    #print("done")
    
    for i in range(1, len(all_nodes)):
        if not all_nodes[i].processed:
            new_subgraph = Graph()
            subset_ids = build_bipartite_graph(i)
            new_subgraph.add_graph(subset_ids)
            subgraphs.append(new_subgraph)

    #print(f"subgraph 0: {subgraphs[0]}")
    
    total_score = 0
    new_edges = []
    result = ""
    
    if len(subgraphs) > 1:
        #print("found multiple graphs")
        
        color_scores = {}

        total_score = 0

        # count colours in graphs. Score white as +1 and black as -1
        for i in range(len(subgraphs)):
            print(f"subgraph {i}: {subgraphs[i]}")
            color_scores[i] = subgraphs[i].count_colors()

        if g_edges != 0 and (len(subgraphs) == 11 or len(subgraphs) == 16 or len(subgraphs) == 18 or len(subgraphs) == 22 or len(subgraphs) == 26):
            sorted_scores = [score for score in color_scores.values()]
            (total_score, combo) = find_smallest_combo(sorted_scores)

            index = 0
            for i, score in color_scores.items():
                # ignore first loop since we don't want to flip the color of the first graph
                if index > 0:
                    # decrement index because it's indexed on the operations between graphs
                    if not combo[index - 1]:
                        subgraphs[i].flip_colors()

                index += 1
        else:
            total_score = 0
            #print("found multiple graphs")
            if g_edges == 0:
                total_score = (len(all_nodes) - 1) % 2
            else:
                # order graphs by absolute score
                sorted_color_scores = {}
                
                sorted_color_scores=dict(sorted(color_scores.items(),key=lambda x:abs(x[1]), reverse = True))
                for i in sorted(color_scores, key=abs):
                    sorted_color_scores[i] = color_scores[i]

                #for node, score in sorted_color_scores.items():
                #    print(f"color score for graph {node}: {score}")
                    
                # go from largest to smallest, trying to get score as close as possible
                # to zero by flipping score
                for i, score in sorted_color_scores.items():
                    option1 = total_score + score
                    option2 = total_score - score
                    
                    if abs(option2) < abs(option1):
                        subgraphs[i].flip_colors()
                        total_score = option2
                    else:
                        total_score = option1
                
                total_score = abs(total_score)

        
        #print(f"total score is {total_score}")
        
        # find 2 nodes from each graph to connect together
        for i in range(1,len(subgraphs)):
            if subgraphs[0].true_color == subgraphs[i].true_color:
                node1 = subgraphs[0].get_first_node_of_color(True)
                node2 = subgraphs[i].get_first_node_of_color(False)
            
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(False)
                    node2 = subgraphs[i].get_first_node_of_color(True)
                
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(True)
                    node2 = subgraphs[i].get_first_node_of_color(True)
                    
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(False)
                    node2 = subgraphs[i].get_first_node_of_color(False)
            else:
                node1 = subgraphs[0].get_first_node_of_color(True)
                node2 = subgraphs[i].get_first_node_of_color(True)
            
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(False)
                    node2 = subgraphs[i].get_first_node_of_color(False)
                
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(False)
                    node2 = subgraphs[i].get_first_node_of_color(True)
                
                if node1 < 0 or node2 < 0:
                    node1 = subgraphs[0].get_first_node_of_color(True)
                    node2 = subgraphs[i].get_first_node_of_color(False)
 
            #print(f"adding edge from node {node1} to {node2}")
            
            new_edges.append([node1,node2])
            result += f"\n{node1} {node2}"

        #print(f"added {len(new_edges)} edges")
    
    result = f"{total_score} {len(new_edges)}" + result

    #print(result)
    
    return result
        
def blackWhiteTree(g_nodes, g_from, g_to):
    global all_nodes
    
    
    if g_edges == 0:
        total_score = (len(all_nodes) - 1) % 2
        result = f"{total_score} {g_nodes-1}"
        for i in range(1,g_nodes):
            result += f"\n{i} {i+1}"
        return result
            

    # all_nodes already has a dummy node at 0
    for i in range(1,g_nodes+1):
        all_nodes.append(Node(i))
    
    for i in range(len(g_from)):
        node1 = g_from[i]
        node2 = g_to[i]
        
        all_nodes[node1].add_edge(all_nodes[node2])
        all_nodes[node2].add_edge(all_nodes[node1])

    results = solve()
    
    return(results)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    g_nodes, g_edges = map(int, input().rstrip().split())

    g_from = [0] * g_edges
    g_to = [0] * g_edges

    for i in range(g_edges):
        g_from[i], g_to[i] = map(int, input().rstrip().split())

    result = blackWhiteTree(g_nodes, g_from, g_to)

    fptr.write(result)
    #fptr.write('\n')

    fptr.close()

n, m = map(int, raw_input().split())

node_adj = [[i] for i in xrange(n)]
node_colors = [0] * n
graph_colors = [-1] * n
node_group = [-1] * n
single_nodes = []

graph_count = 0

edges = []
for _ in xrange(m):
    s = raw_input()
    edges.append(s)
    node1, node2 = map(int, s.split())
    node_adj[node1 - 1].append(node2 - 1)
    node_adj[node2 - 1].append(node1 - 1)
    
for node, adjs in enumerate(node_adj):
    adj_len = len(adjs)
    if adj_len == 1:
        single_nodes.append(node)
    elif adj_len > 1:
        node_group[node] = node
        delta = 1
        graph_count += 1
        node_colors[node] = 1
        for adj in adjs:
            if adj == node:
                continue
            node_colors[adj] = node_colors[node] * -1
            node_group[adj] = node
        for adj in adjs:
            if adj == node:
                continue
            node_group[adj] = node
            delta += node_colors[adj]
            child_adjs = node_adj[adj]
            node_adj[adj] = []
            for child_adj in child_adjs:
                if child_adj == adj:
                    continue
                if node_group[child_adj] == node:
                    continue
                adjs.append(child_adj)
                node_colors[child_adj] = node_colors[adj] * -1
                node_group[child_adj] = node
        if delta < 0:
            for adj in adjs:
                node_colors[adj] = -node_colors[adj]
        graph_colors[node] = abs(delta)

color_count = {}
for gc_idx, gc_cnt in enumerate(graph_colors):
    if gc_cnt <= 0:
        continue
    graphs = color_count.get(gc_cnt, [])
    graphs.append(gc_idx)
    color_count[gc_cnt] = graphs

color_sum = sum([d for d in graph_colors if d > 0])
half_sum = int(color_sum / 2)
offs = color_sum % 2
single_node_cnt = len(single_nodes)
low_level = half_sum - single_node_cnt/2
high_level = half_sum

fin_pos = -1
if color_sum > 0:
    d_calc = [[0, -1, -1] for i in xrange(color_sum)]
    d_calc[0][0] = 1
    finish = False
    for gc_cnt, graphs in color_count.items():
        for i, sum_info in enumerate(d_calc):
            if i > half_sum:
                break
            if sum_info[0] == 1:
                continue
            if i - gc_cnt < 0:
                continue
            if d_calc[i - gc_cnt][0] == 0:
                continue
            if d_calc[i - gc_cnt][1] == gc_cnt:
                cnt = d_calc[i - gc_cnt][2]
                if cnt == 0:
                    continue
            else:
                cnt = len(graphs)
            d_calc[i] = [1, gc_cnt, cnt - 1]
            if low_level <= i <= high_level:
                finish = True
                fin_pos = i
        if finish:
            break
    if not finish:
        for i, sum_info in enumerate(d_calc[low_level-1::-1]):
            if sum_info[0] == 0:
                continue
            fin_pos = low_level - 1 - i
            break

d1 = color_sum if fin_pos < 0 else color_sum - 2 * (fin_pos + 0)
d = ((single_node_cnt - d1) % 2) if single_node_cnt >= d1 else (d1 - single_node_cnt)
inverted_single_cnt = ((single_node_cnt + d1) / 2) if single_node_cnt > d1 else single_node_cnt
k = graph_count + single_node_cnt - 1

'''
print("fin_pos={}, low_level={}, high_level={}".format(fin_pos, low_level, high_level))
print(color_count)
print("single_node_cnt={}, graph_count={}, color_sum={}, half_sum={}".format(single_node_cnt, graph_count, color_sum, half_sum))
print("d1={}, d={}, inverted_single_cnt={}, k={}".format(d1, d, inverted_single_cnt, k))
'''

graph_invert = [1] * n

black_sum = 0
while fin_pos > 0:
    sum_info = d_calc[fin_pos]
    gc_cnt = sum_info[1]
    black_sum += gc_cnt
    idx = sum_info[2]
    gc_idx = color_count[gc_cnt][idx]
    graph_invert[gc_idx] = -1
    fin_pos -= gc_cnt

print("{} {}".format(d, k))
#print("{} {}".format(n, k+m))
#for edge in edges:
#    print(edge)

if graph_count > 0:
    for gc_idx, gc_cnt in enumerate(graph_colors):
        if gc_cnt < 0:
            continue
        white_node_idx, black_node_idx = gc_idx, node_adj[gc_idx][1]
        if graph_invert[gc_idx] * node_colors[gc_idx] < 0:
            white_node_idx, black_node_idx = black_node_idx, white_node_idx
        '''
        if (graph_invert[gc_idx] < 0):
            ####
            for adj in node_adj[gc_idx]:
                node_colors[adj] = node_colors[adj] * -1
            ####
        '''
        for idx, cnt in enumerate(graph_colors):
            if idx <= gc_idx:
                continue
            if cnt < 0:
                continue
            ''''''
            if graph_invert[idx] * node_colors[idx] > 0:
                print("{} {}".format(black_node_idx + 1, node_group[idx] + 1))
            else:
                print("{} {}".format(white_node_idx + 1, node_group[idx] + 1))
            '''
            if (graph_invert[idx] < 0):
                ####
                for adj in node_adj[idx]:
                    node_colors[adj] = node_colors[adj] * -1
                ####
            '''
        for s_idx, s_node in enumerate(single_nodes):
            if s_idx < inverted_single_cnt:
                ####
                #node_colors[s_node] = -1
                ####
                print("{} {}".format(white_node_idx + 1, s_node + 1))
            else:
                ####
                #node_colors[s_node] = 1
                ####
                print("{} {}".format(black_node_idx + 1, s_node + 1))
        break
else:
    for s_idx, s_node in enumerate(single_nodes[:-1:]):
        print("{} {}".format(s_node + 1, single_nodes[s_idx + 1] + 1))

#print("delta={}".format(sum(node_colors)))
#print("black_sum={}".format(black_sum))

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 1234555
typedef struct _node{
  int t;
  int i;
  int c;
  int a;
  struct _node *next;
} node;
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
int abss(int x);
void insert_edge(int x,int y,int w);
void dfs(int x,int c);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
void sort_a_ad(int*a,int*c,int size,int*new_size);
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
void insert(int target,int idx,int c,int a);
int search(int target,int idx,int *c);
int solve(int target,int target2,int idx);
void clean_table();
int N,w,b,ngs,*cans,*cdiff,*c,idx[200000],*trace,mark[200000]={0},diff[200000],f[200000],s[200000],*remain;
lnode **table;
node *hash[HASH_SIZE]={0};

int main(){
  int M,x,y,gs,sum,ans,target,i,j,k;
  scanf("%d%d",&N,&M);
  table=(lnode**)malloc(N*sizeof(lnode*));
  memset(table,0,N*sizeof(lnode*));
  for(i=0;i<M;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,1);
  }
  trace=(int*)malloc(N*sizeof(int));
  memset(trace,0,N*sizeof(int));
  for(i=gs=0;i<N;i++)
    if(!trace[i]){
      w=b=0;
      dfs(i,0);
      x=i;
      if(table[i])
        y=table[i]->x;
      else
        y=-1;
      if(w>b){
        diff[gs]=w-b;
        f[gs]=x;
        s[gs]=y;
      }
      else{
        diff[gs]=b-w;
        f[gs]=y;
        s[gs]=x;
      }
      idx[gs]=gs;
      gs++;
    }
  free(trace);
  clean_table();
  free(table);
  cdiff=(int*)malloc(gs*sizeof(int));
  c=(int*)malloc(gs*sizeof(int));
  for(i=sum=0,ans=200001;i<gs;i++){
    sum+=diff[i];
    cdiff[i]=diff[i];
    c[i]=1;
  }
  target=sum/2;
  sort_a2(diff,idx,gs);
  sort_a_ad(cdiff,c,gs,&ngs);
  remain=(int*)malloc(ngs*sizeof(int));
  if(!M || ngs==1){
    printf("%d %d\n",gs%2*cdiff[0],gs-1);
    for(i=0;i<gs-1;i++)
      printf("%d %d\n",f[i]+1,f[i+1]+1);
    return 0;
  }
  for(i=0;i<ngs;i++)
    if(i==0)
      remain[i]=c[i]*cdiff[i];
    else
      remain[i]=remain[i-1]+c[i]*cdiff[i];
  ans=solve(target,(sum+1)/2,ngs-1);
  cans=remain;
  memset(cans,0,ngs*sizeof(int));
  for(i=ngs-1;i>=0;i--){
    if(target<=0)
      break;
    if(i==0){
      cans[i]=(target-1)/cdiff[i]+1;
      break;
    }
    search(target,i,&cans[i]);
    if(cans[i]==-1){
      for(j=i;j>=0;j--)
        cans[j]=c[j];
      break;
    }
    target-=cans[i]*cdiff[i];
  }
  for(j=0,k=0;j<gs && k<ngs;k++){
    x=j+cans[k];
    for(;j<x;j++)
      mark[j]=1;
    while(diff[j]==cdiff[k] && j<gs)
      j++;
  }
  printf("%d %d\n",abss(2*ans-sum),gs-1);
  for(i=0;i<gs;i++)
    if(s[idx[i]]!=-1)
      k=i;
  for(i=0;i<gs;i++){
    if(i==k)
      continue;
    if(mark[i]!=mark[k])
      printf("%d %d\n",f[idx[i]]+1,f[idx[k]]+1);
    else
      printf("%d %d\n",f[idx[i]]+1,s[idx[k]]+1);
  }
  return 0;
}
int abss(int x){
  return (x<0)?-x:x;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs(int x,int c){
  lnode *p;
  trace[x]=1;
  if(c)
    b++;
  else
    w++;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x])
      dfs(p->x,c^1);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a_ad(int*a,int*c,int size,int*new_size){
  if (size < 2){
    (*new_size)=size;
    return;
  }
  int m = (size+1)/2,i;
  int *left_a,*right_a,*left_c,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_c[i]=c[i+m];
  }
  int new_l_size=0,new_r_size=0;
  sort_a_ad(left_a,left_c,m,&new_l_size);
  sort_a_ad(right_a,right_c,size-m,&new_r_size);
  merge_ad(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
  free(left_a);
  free(right_a);
  free(left_c);
  free(right_c);
  return;
}
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
  int i = 0, j = 0,index=0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    } else if (j == right_size) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    }
    if(index>1&&a[index-2]==a[index-1]){
      c[index-2]+=c[index-1];
      index--;
    }
  }
  (*new_size)=index;
  return;
}
void insert(int target,int idx,int c,int a){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t;
  t=(node*)malloc(sizeof(node));
  t->t=target;
  t->i=idx;
  t->c=c;
  t->a=a;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
int search(int target,int idx,int *c){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->t==target && t->i==idx){
      *c=t->c;
      return t->a;
    }
    t=t->next;
  }
  return -1;
}
int solve(int target,int target2,int idx){
  if(target<=0)
    return 0;
  if(target>remain[idx])
    return -1;
  if(target==remain[idx]){
    insert(target,idx,-1,target);
    return target;
  }
  int t,ans=200000,ansc,i;
  if(idx==0){
    t=(target-1)/cdiff[idx]+1;
    return t*cdiff[idx];
  }
  t=search(target,idx,&w);
  if(t!=-1)
    return t;
  for(i=0;i<=c[idx];i++){
    t=solve(target-i*cdiff[idx],target2-i*cdiff[idx],idx-1);
    if(t!=-1){
      if(t+i*cdiff[idx]<ans){
        ans=t+i*cdiff[idx];
        ansc=i;
      }
      if(t+i*cdiff[idx]==target || t+i*cdiff[idx]==target2){
        insert(target,idx,i,t+i*cdiff[idx]);
        return t+i*cdiff[idx];
      }
    }
    if(target-i*cdiff[idx]<=0)
      break;
  }
  insert(target,idx,ansc,ans);
  return ans;
}
void clean_table(){
  int i;
  lnode *p,*pp;
  for(i=0;i<N;i++)
    if(table[i]){
      p=table[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      table[i]=NULL;
    }
  return;
}