// Arup Guha
// 3/25/2015
// Solution to 2014 USACO Open Bronze Problem: Decorating the Pastures

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

public class decorate {

	final public static int NO_COLOR = 0;
	final public static int J_SIGN = 1;
	final public static int F_SIGN = 2;

	public static ArrayList[] graph;
	public static int[] colors;
	public static int n;

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new FileReader("decorate.in"));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		int e = Integer.parseInt(tok.nextToken());

		// Set up graph.
		graph = new ArrayList[n];
		for (int i=0; i<n; i++)
			graph[i] = new ArrayList<Integer>();

		// Read in graph.
		for (int i=0; i<e; i++) {
			tok = new StringTokenizer(stdin.readLine());
			int v1 = Integer.parseInt(tok.nextToken())-1;
			int v2 = Integer.parseInt(tok.nextToken())-1;
			graph[v1].add(v2);
			graph[v2].add(v1);
		}

		// Uncolored.
		colors = new int[n];

		// Try to two color it.
		boolean result = color();

		// Write out the result.
		FileWriter fout = new FileWriter(new File("decorate.out"));
		if (!result) fout.write("-1\n");
		else fout.write(freq(J_SIGN)+"\n");
		fout.close();
	}

	// Return the number of times sign occurs in the array colors.
	public static int freq(int sign) {
		int res = 0;
		for (int i=0; i<n; i++)
			if (colors[i] == sign)
				res++;
		return res;
	}

	public static boolean color() {

		// Try each node.
		for (int i=0; i<n; i++) {

			boolean cur = true;

			// Start coloring from here if it's not colored.
			if (colors[i] == NO_COLOR)
				cur = bfsColor(i);

			// Oops had a problem with this component.
			if (!cur) return false;
		}

		// Made it here, so we're good.
		return true;
	}

	public static boolean bfsColor(int node) {

		// Keeping track of what we've colored in THIS component.
		HashSet<Integer> used = new HashSet<Integer>();

		// Queue for bfs.
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.offer(node);
		used.add(node);
		colors[node] = J_SIGN;

		int jCount = 1, fCount = 0;

		// Run BFS.
		while (q.size() > 0) {

			// Get next item.
			int next = q.poll();

			// Go through ALL edges.
			for (int i=0; i<graph[next].size(); i++) {

				// Easy name for neighbor.
				int item = (Integer)graph[next].get(i);

				// Oops contradiction!
				if (used.contains(item) && colors[item] == colors[next]) return false;

				// Put in queue and color it.
				else if (!used.contains(item)) {
					q.offer(item);
					used.add(item);
					colors[item] = colors[next] == J_SIGN ? F_SIGN : J_SIGN;

					// Also, update out counts.
					if (colors[item] == J_SIGN) jCount++;
					else                        fCount++;
				}
			}
		}

		// Need to flip colors...
		if (jCount < fCount) {

			// Go through colored nodes efficiently, flipping all.
			for (Integer index : used) {
				if (colors[index] == F_SIGN) colors[index] = J_SIGN;
				else						 colors[index] = F_SIGN;
			}
		}


		// If we make it here, we're good.
		return true;
	}
}