fn.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
 
using namespace std;
typedef set<int> SET;
typedef SET::iterator IT;
 
typedef struct EDGE
{
	int u;
	int v;
}
EDGE;
 
EDGE Input[100000];
 
int Degree[100000];
int Fol[100000];
int iFol[100000];
int CurIndex[100000];
 
int Visited[100000];
int List[100000]; //D3
int nList;
 
int Q[100000];
int QBeg, QEnd;
 
int main()
{
	int n, m, mm;
	while(scanf("%d%d", &n, &m) > 0)
	{
		memset(Degree, 0, sizeof(Degree));
		memset(CurIndex, 0, sizeof(CurIndex));
		memset(Visited, 0, sizeof(Visited));
 
		for(int i = 0; i < m; i++)
		{
			scanf("%d%d", &(Input[i].u), &(Input[i].v));
			Input[i].u--;
			Input[i].v--;
 
			Input[i + m].u = Input[i].v;
			Input[i + m].v = Input[i].u;
 
			Degree[Input[i].u]++;
			Degree[Input[i].v]++;
		}
 
		iFol[0] = 0;
		for(int i = 0; i < n; i++)
		{
			iFol[i + 1] = iFol[i] + Degree[i];
 
			if(Degree[i] >= 4)
			{
				printf("YES\n");
				goto NEXT_INSTANCE;
			}
		}
 
		mm = m * 2;
		for(int i = 0; i < mm; i++)
		{
			int e = Input[i].u;
			Fol[iFol[e] + CurIndex[e]++] = Input[i].v;
		}
 
		for(int i = 0; i < n; i++)
		//components
		{
			if(Visited[i])
			{
				continue;
			}
 
			nList = 0;
			QBeg = 0;
			QEnd = 0;
			Q[QEnd++] = i;
 
			while(QBeg < QEnd)
			{
				int cur = Q[QBeg++];
				for(int j = iFol[cur]; j < iFol[cur + 1]; j++)
				{
					int t = Fol[j];
 
					if(!(Visited[t]))
					{
						Visited[t] = 1;
						Q[QEnd++] = t;
					}
				}
			}
 
			for(int j = 0; j < QEnd; j++)
			{
				if(Degree[Q[i]] == 3)
				{
					List[nList++] = Q[i];
				}
			}
 
			for(int j = 0; j < nList; j++)
			{
				for(int k = j + 1; k < nList; k++)
				{
					int u = List[j];
					int v = List[k];
 
					SET set;
					set.insert(Fol[iFol[u] + 0]);
					set.insert(Fol[iFol[u] + 1]);
					set.insert(Fol[iFol[u] + 2]);
					set.insert(Fol[iFol[v] + 0]);
					set.insert(Fol[iFol[v] + 1]);
					set.insert(Fol[iFol[v] + 2]);
 
					if(set.find(u) == set.end())
					//nesousedi
					{
						if(set.size() >= 5)
						{
							printf("YES\n");
							goto NEXT_INSTANCE;
						}
					}
					else
					//sousedi
					{
						if(set.size() >= 6)
						{
							printf("YES\n");
							goto NEXT_INSTANCE;
						}
					}
				}
			}
		}
 
		printf("NO\n");
		NEXT_INSTANCE:;
	}
 
	return 0;
}