/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
/**
*
* @author cteam92
*/
public class Fn {
static ArrayList<LinkedList<Integer>> graph;
static int n, m;
static boolean[] visited;
static int[] components;
static void markComponents() {
components = new int[n];
visited = new boolean[n];
for (int i = 0; i < n; i++) {
dfs(i, i);
}
}
static void dfs(int node, int leader) {
if (visited[node]) {
return;
}
visited[node] = true;
components[node] = leader;
for (Integer neighbour
: graph.
get(node
)) { dfs(neighbour, leader);
}
}
public static void main
(String[] args
) { Scanner sc
= new Scanner
(System.
in); while (true) {
int V1, V2;
if (!sc.hasNext()) {
break;
}
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
graph = new ArrayList<LinkedList<Integer>>();
for (int i = 0; i < n; i++) {
graph.add(new LinkedList<Integer>());
}
for (int i = 0; i < m; i++) {
V1 = sc.nextInt();
V2 = sc.nextInt();
sc.nextLine();
LinkedList<Integer> vertex;
vertex = graph.get(V1 - 1);
vertex.add(V2 - 1);
graph.set(V1 - 1, vertex);
vertex = graph.get(V2 - 1);
vertex.add(V1 - 1);
graph.set(V2 - 1, vertex);
}
/*System.out.println("----");
for (int i=0; i<n; i++) {
System.out.println(graph.get(i).toString());
}*/
markComponents();
//System.out.println(Arrays.toString(components));
//Set<Integer> withY = new HashSet<Integer>();
Map
<Integer, Set
<Integer
>> yNodes
= new HashMap
<Integer, Set
<Integer
>>(); for (int i = 0; i < n; i++) {
yNodes.put(i, new HashSet<Integer>());
}
boolean bunny = false;
for (int node = 0; node < n; node++) {
int neighbourCount = graph.get(node).size();
if (neighbourCount >= 4) {
bunny = true;
break;
} else if (neighbourCount == 3) {
Set<Integer> nodeSet = new HashSet<Integer>(graph.get(node));
for (int i : yNodes.get(components[node])) {
Set<Integer> nodeYSet = new HashSet<Integer>(graph.get(i));
//System.out.println("nodeYSet pro " + i + " " + nodeYSet.toString());
if (nodeYSet.contains(node)) {
//System.out.println("sousedi" + i + " " + node);
nodeYSet.retainAll(nodeSet);
//System.out.println("po pruniku" + nodeYSet.toString());
if (nodeYSet.isEmpty()) {
//System.out.println("1");
bunny = true;
break;
}
} else {
//System.out.println("nejsou sousedi" + i + " " + node);
nodeYSet.retainAll(nodeSet);
//System.out.println("po pruniku" + nodeYSet.toString());
if (nodeYSet.size() <= 1) {
//System.out.println("2");
bunny = true;
break;
}
}
}
if (bunny) break;
yNodes.get(components[node]).add(node);
}
}
if (bunny) {
} else {
}
}
}
}