import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int applyNum = in.nextInt();
        //构建图
        Graph g = new Graph(count);
        for (int i = 0; i < applyNum; ++i) {
            int a = in.nextInt();
            int b = in.nextInt();
            g.addEdges(a - 1, b - 1);
        }

        //染色
        for (int node : g.nodes) {
            if (g.colors[node] == 0) {
                if (!dfs(g, node, 1)) {
                    System.out.print(0);
                    return;
                }
            }
        }

        System.out.print(1);

    }
    public static boolean dfs(Graph g, int node, int color) {
        if (g.colors[node] == 0) {
            g.colors[node] = color;
            List<Integer> neighbors = g.getNeighbors(node);
            for (int i : neighbors) {
                if (!dfs(g, i, 3 - color)) return false;
            }
            return true;
        } else {
            return g.colors[node] == color;
        }
    }
}

class Graph {
    int nodesCount = 0;
    int[] nodes;
    int[] colors;
    int[][] edges;
    public Graph(int nodesCount) {
        this.nodesCount = nodesCount;
        nodes = new int[nodesCount];
        colors=new int[nodesCount];
        for (int i = 0; i < this.nodesCount; i++) {
            nodes[i] = i;
        }
        edges = new int[nodesCount][nodesCount];
    }
    public void addEdges(int i, int j) {
        edges[i][j] = 1;
        edges[j][i] = 1;
    }

    public List<Integer> getNeighbors(int node) {
        int[] allNodes = edges[node];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < this.nodesCount; ++i) {
            if (allNodes[i] == 1) {
                list.add(i);
            }
        }
        return list;
    }
}