Cycle of Four in Secret Tunnels

You are given an undirected graph representing a network of secret tunnels among chambers. The graph consists of n chambers (numbered from 1 to n) and m tunnels. Each tunnel connects two distinct chambers. Your task is to determine whether there exists a cycle that involves exactly four distinct chambers such that the cycle is formed by four tunnels.

A valid cycle of four chambers is defined by four distinct nodes \(a, b, c, d\) with edges \((a,b)\), \((b,c)\), \((c,d)\) and \((d,a)\). Note that a simple cycle of four nodes without any additional tunnels does not qualify if your algorithm only finds cycles with additional connectivity. In this problem, based on the underlying approach, a cycle is detected if there exists an edge \((u,v)\) that has at least two common neighbours. If such a condition is met, print YES otherwise print NO.

It is guaranteed that the input graph does not contain self-loops or multiple edges between the same pair of chambers.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

where the first line contains two integers: n and m. Each of the next m lines contains two integers u and v indicating that there is a tunnel connecting chamber u and chamber v.

outputFormat

Output a single line to standard output (stdout) containing YES if there exists a cycle of four distinct chambers as described, or NO otherwise.

6 7
1 2
1 3
2 3
2 4
3 4
4 5
5 6

YES