幼儿园分班

import java.util.*;
public class Main {
 public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();//小朋友人数
    int q=sc.nextInt();//请求数量
    List<Integer> list1=new ArrayList<Integer>();//分班1
    List<Integer> list2=new ArrayList<Integer>();//分班1
    int[][] quest=new int[q][3];//多留一列，用来表示这个请求是否已经被处理0，未处理，2，已处理，1经过一次过滤
    for (int i = 0; i <q ; i++) {
      quest[i][0]=sc.nextInt();
      quest[i][1]=sc.nextInt();
    }
    //预处理
    list1.add(quest[0][0]);
    list2.add(quest[0][1]);
    quest[0][2]=1;
    int count=0;
    while(list1.size()+list2.size()<n){
         count++;
         if(count>2*q) break;
        for (int i = 1; i <q ; i++) {
          if(quest[i][2]<=1){
            if(list1.contains(quest[i][0])){
              if(list1.contains(quest[i][1])){
                count=2*q+1;
                break;
              }
              list2.add(quest[i][1]);
              quest[i][2]=2;
            }else if(list1.contains(quest[i][1])){
              if(list1.contains(quest[i][0])){
                count=2*q+1;
                break;
              }
              list2.add(quest[i][0]);
              quest[i][2]=2;
            }else if(list2.contains(quest[i][1])){
              if(list2.contains(quest[i][0])){
                count=2*q+1;
                break;
              }
              list1.add(quest[i][0]);
              quest[i][2]=2;
            } else if(list2.contains(quest[i][0])){
              if(list2.contains(quest[i][1])){
                count=2*q+1;
                break;
              }
              list1.add(quest[i][1]);
              quest[i][2]=2;
            }else if(quest[i][2]==0){
              quest[i][2]=1;
            }else{
              list1.add(quest[i][0]);
              list2.add(quest[i][1]);
            }

        }
      }

    }
    if(count<=2*q)
      System.out.println(1);
    else
      System.out.println(0);
  }
}