import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Bipartite {
    private static int bipartite(ArrayList<Integer>[] adj) {

        boolean bipartiteCheckNodes = bfsBipartiteCheck(adj, 0);
        if (bipartiteCheckNodes)
            return 1;
        else
            return 0;
    }

    private static boolean bfsBipartiteCheck(ArrayList<Integer>[] adj, int s) {
        if (adj[s].size() == 0)
            return true;
        int[] dist = new int[adj.length];

        Arrays.fill(dist, -1);

        dist[s] = 0;

        Queue<Integer> vertexQ = new LinkedList<>();
        vertexQ.add(s);

        while (!vertexQ.isEmpty()) {
            int u = vertexQ.remove();
            for (int i : adj[u])
                if (dist[i] == -1) {
                    vertexQ.add(i);
                    if (dist[u] == 0)
                        dist[i] = 1;
                    if (dist[u] == 1)
                        dist[i] = 0;
                } else if (dist[i] == dist[u]) {
                    return false;
                }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            x = scanner.nextInt();
            y = scanner.nextInt();
            adj[x - 1].add(y - 1);
            adj[y - 1].add(x - 1);
        }
        System.out.println(bipartite(adj));
    }
}