[SGU513] Maximal Clique

题目描述

你得到了一张无向图，需要判断它是否可能由下面这个经典的 3-SAT 到最大团问题的规约产生。

设原来的 3-CNF 公式有 $n$ 个子句，每个子句恰好包含三个文字，并且同一子句中的三个文字对应三个不同的布尔变量。对于每个子句中的每个文字建立一个顶点，因此一共有 $3n$ 个顶点。

对于属于不同子句的两个顶点：如果它们对应的两个文字不矛盾，就在它们之间连边。这里“不矛盾”是指：它们不是同一个变量的一正一反两个文字。属于同一子句的两个顶点之间不连边。

最后，可以任意重新编号这些顶点。

给定一张无向图，请判断是否存在某个满足上述要求的 3-CNF 公式，使得经过这个规约后恰好得到给定图。

输入格式

第一行包含两个整数 $v,e$，表示图的顶点数和边数，$1\le v\le100$。

接下来 $e$ 行，每行包含两个整数 $a,b$，表示顶点 $a,b$ 之间有一条无向边。保证没有自环和重边。

输出格式

如果给定图可能由上述规约得到，输出 YES；否则输出 NO。

样例

样例输入

9 22
1 3
1 6
7 1
8 9
9 1
2 3
2 4
2 5
2 6
2 8
3 4
3 5
3 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 9
7 8

样例输出

YES