One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

Input

The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

Output

Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

Examples

Input

5 4
1 2
2 4
5 3
1 4


Output

1

Input

6 2
1 4
3 4


Output

0

Input

6 6
1 2
2 3
3 1
4 5
5 6
6 4


Output

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

public class Main {

    public static void main(String[] args) {
        InputStream inS = System.in;
//        InputReader sc = new InputReader(inS);
        PrintStream out = System.out;
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt();
        Graph g = new Graph(n);

        for (int i = 0; i < m; i++) {
            g.addEdge(sc.nextInt()-1, sc.nextInt()-1);
        }

        Bipartite b = new Bipartite(g);
        out.println((n - b.oddCycles()) % 2 != 0 ? (b.oddCycles() + 1) : b.oddCycles());
        out.close();
    }


public static class Graph {

    private LinkedList<Integer>[] graph;
    private int V;
    private int E;

    public Graph(int N) {
        V = N;
        E = 0;
        graph = (LinkedList<Integer>[]) new LinkedList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new LinkedList<>();
        }
    }


    public void addEdge(int u, int v) {
        graph[u].add(v);
        graph[v].add(u);
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return graph[v];
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public String toString() {
        StringBuilder str = new StringBuilder();

        for (int v = 0; v < V(); v++) {
            for (int w : adj(v)) {
                str.append(v);
                str.append("<->");
                str.append(w);
                str.append(" ");
            }
            str.append('\n');
        }

        return str.toString();
    }

    public static int degree(Graph g, int v) {
        return g.graph[v].size();
    }

    public static int maxDegree(Graph g) {
        int max = 0;
        for (int v = 0; v < g.V(); v++) {
            if (degree(g, v) > max) {
                max = degree(g, v);
            }
        }

        return max;
    }

    public static double averageDegree(Graph g) {
        return 2.0 * g.E() / g.V();
    }

    public static int numberOfSelfLoops(Graph g) {
        int count = 0;
        for (int v = 0; v < g.V(); v++) {
            for (int w : g.adj(v)) {
                if (v == w) {
                    count++;
                }
            }
        }

        return count / 2; // cuz each edge is counted twice
    }
}

    public static class Bipartite {
        private boolean marked[];
        private Graph G;
        private boolean[] color;
        private boolean isBipartite;
        private int[] edgeTo;
        private int count;

        public Bipartite(Graph G) {
            this.G = G;
            this.count = 0;

            color = new boolean[G.V()];
            marked = new boolean[G.V()];
            edgeTo = new int[G.V()];

            for (int w = 0; w < G.V(); w++) {
                if (!marked[w]) {
                    isBipartite = true;
                    dfs(w);
                }
            }
        }
        

        private void dfs(int vertex) {
            marked[vertex] = true;
            for (int i : this.G.adj(vertex)) {
                if (!isBipartite) {
                    return;
                }

                if (!marked[i]) {
                    color[i] = !color[vertex];
                    edgeTo[i] = vertex;
                    dfs(i);
                } else if (color[i] == color[vertex]) {
                    isBipartite = false;
                    count++;
                    return;
                }
            }
        }

        public int oddCycles() {
            return count;

        }
    }

//    public static class Cycle {
//        private boolean[] marked;
//        private int[] edgeTo;
//        private Stack<Integer> cycle;
//        private Graph G;
//        private int count;
//
//        public Cycle(Graph g) {
//            G = g;
//            marked = new boolean[G.V()];
//            edgeTo = new int[G.V()];
//
//            for (int v = 0 ; v < G.V() ; v++) {
//                if (!marked[v]) {
//                    dfs(-1, v);
//                }
//            }
//        }
//
//        private boolean hasSelfLoops() {
//            for (int v = 0 ; v < G.V() ; v++) {
//                for (int w : G.adj(v)) {
//                    if (v == w) {
//                        cycle = new Stack<>();
//                        cycle.push(v);
//                        cycle.push(v);
//                        return true;
//                    }
//                }
//            }
//
//            return false;
//        }
//
//        private boolean hasParallelEdges() {
//            for (int v = 0 ; v < G.V() ; v++) {
//                for (int w : G.adj(v)) {
//                    if (marked[w]) {
//                        cycle = new Stack<>();
//                        cycle.push(v);
//                        cycle.push(w);
//                        cycle.push(v);
//                        return true;
//                    }
//                    marked[w] = true;
//                }
//
//                for (int w : G.adj(v)) {
//                    marked[w] = false;
//                }
//            }
//
//            return false;
//        }
//
//        private void dfs(int parent , int vertex) {
//            marked[vertex] = true;
//
//            for (int i : this.G.adj(vertex)) {
//                if (hasCycle()) {
//                    return ;
//                }
//
//                if (!marked[i]) {
//                    edgeTo[i] = vertex;
//                    dfs(vertex, i);
//                } else if (i != parent){
//                    cycle = new Stack<>();
//                    for (int w = vertex ; w != i ; w = edgeTo[w]) {
//                        cycle.push(w);
//                    }
//                    cycle.push(i);
//                    count = cycle.size() % 2 != 0 ? (count + 1) : count;
//                    return;
//                }
//            }
//        }
//
//        public Iterable<Integer> cycle() {
//            return cycle;
//        }
//
//        public boolean hasCycle() {
//            return cycle != null;
//        }
//
//        private int oddCycles() {
//            return count;
//        }
//    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

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

    }

}
