Finding cliques

Finding cliques

A classical problem in graph theory involves finding cliques. Consider an undirected graph with n vertices. A clique is a complete subgraph - i.e., it is a set of k nodes such that all possible edges between these k nodes exist. This problem asks you if a clique exists in a given graph. To make things simple your are told that k = 4, i.e., you are looking for a clique of size 4.


The input will contain multiple instances. The first line of each instance has two integers - the number of nodes n (n < 20) and the number of edges m (m < 100). The second line has m pairs of numbers each denoting an undirected edge. The nodes are labeled from 1 to n. You may assume there are no repeats in the edge list. The last line contains 0 0 and should not be processed.


The output should contain one line for each case. Each line should have a YES or a NO, depending on whether there is a clique of size 4 or not.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 6
1 2 2 3 3 4 4 1 1 3 2 4
0 0
Output example #1