백준 13023 : ABCDE

#인접 리스트 구현
n, m = map(int,input().split())

adj = [[] for _ in range(n)]

for i in range(m):
  src, dest = map(int,input().split())
  adj[src].append(dest)
  adj[dest].append(src)


#해당 그래프의 깊이가 5임을 확인
depth_list = []

def dfs(v,depth,visited):
  if depth>=6:
    return
  global depthlist
  visited[v] = True
  depth_list.append(depth)
  for i in adj[v]:
    if not visited[i]:
      dfs(i,depth+1,visited)
  visited[v] = False #중요!

result = 0
for i in range(n):
  #print("Case: Treenode is "+str(i))
  visited = [False]*n
  dfs(i,1,visited)
  depth_list.sort()
  depth_list.reverse()
  if depth_list[0]>=5:
    result = 1
    break
  #print(">depth : "+str(depth_list[0]))
  depth_list = []
print(result)


'''
주요 반례:
[[1],[2,3],[1,3],[1,2],[3]]
단순 DFS로 풀면 조건에 부합하지 않는다