// Arup Guha
// 11/13/2017
// Solution to 2017 SER D1 Problem: Unsatisfying

import java.util.*;

public class unsatisfying {

	public static int n;
	public static ArrayList[] g;
	public static boolean[][] canReach;

	public static void main(String[] args) {

		// Set up implication graph.
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		int numC = stdin.nextInt();
		g = new ArrayList[2*n];
		for (int i=0; i<2*n; i++) g[i] = new ArrayList<Integer>();

		// Add in 2 edges for each clause.
		for (int i=0; i<numC; i++) {
			int v1 = map(stdin.nextInt());
			int v2 = map(stdin.nextInt());
			g[not(v1)].add(v2);
			g[not(v2)].add(v1);
		}

		// Ta da!
		System.out.println(solve());
	}

	public static int solve() {

		boolean gotForward = false;

		// We'll mark everywhere we can reach here.
		canReach = new boolean[2*n][2*n];

		// Try DFS from each node since the bounds are small enough!
		for (int i=0; i<n; i++) {
			boolean forward = dfsWrapper(i);
			boolean back = dfsWrapper(not(i));

			// This means both a -> not(a) AND not(a) -> a. Impossible!
			if (forward && back) return 0;

			// We have a forward implication, make note if it.
			if (forward) gotForward = true;
		}

		// Whatever variable has a -> not(a), we can just add the clause (a or a).
		if (gotForward) return 1;

		// These are criss-cross implications; a->not(b) and b->not(a)
		// We can just add (a or a) and (b or b) so the cycle a->not(b)->b->not(a)->a exists.
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				if (canReach[i][not(j)] && canReach[j][not(i)])
					return 2;

		// If none of those options worked, we can't do it!
		return -1;
	}

	// Runs a dfs from v and returns true iff it gets to not(v).
	public static boolean dfsWrapper(int v) {
		return dfs(v, not(v), canReach[v]);
	}

	// Returns true iff we can go from u to v. used marks where we've been.
	public static boolean dfs(int u, int v, boolean[] used) {

		// Done!
		if (u == v) return true;

		// Mark it.
		used[u] = true;

		boolean ret = false;

		// Go to neighbors - call first then or with ret so dfs doesn't get short circuited.
		for (int next : (ArrayList<Integer>)g[u])
			if (!used[next])
				ret = dfs(next, v, used) || ret;

		return ret;
	}

	public static int map(int v) {
		return v > 0 ? v-1 : n-v-1;
	}

	public static int not(int v) {
		return v < n ? v+n : v-n;
	}
}