Part Assembly Machine

The mysterious inventor SHTSC, famous for his laser generator, has now unveiled a new invention: the Part Assembly Machine — a device that can produce and assemble parts.

A part is defined as an undirected graph whose vertices are labeled from \(0\) to \(n-1\). The machine has two functions:

1. Production: It produces a part consisting of exactly one vertex (labeled \(0\)) and no edges.
2. Composition: It combines two existing parts \(G_1\) and \(G_2\), with the condition that the number of vertices in \(G_2\) (say \(m\)) is greater than or equal to the number of vertices in \(G_1\) (say \(n\)). The resulting part \(G\) is defined as follows:
   • The vertex set of \(G\) is the union of the vertex sets of \(G_1\) and \(G_2\). In the process, every vertex \(i\) (with \(0 \le i < m\)) of \(G_2\) is re-labeled as \(n+i\).
   • The edge set of \(G\) is the union of the edge sets of \(G_1\) and \(G_2\), plus for every vertex \(a\) with \(a \ge n\) (i.e. every vertex coming from \(G_2\) after the shift), an extra undirected edge \((a, a \bmod n)\) is added. In \(\LaTeX\) format, this extra edge rule is given by: \(\forall i \in \{0,1,\ldots,m-1\}, \text{ add edge } (n+i,\; (n+i)\bmod n)\).

Note that parts are labeled graphs. That is, even if two parts have the same structure but different vertex labels, they are considered different.

Your task is: Given a part (an undirected graph with vertices labeled \(0 \ldots N-1\)), determine whether it can be produced by the Part Assembly Machine using a sequence of the two operations described above.

Input/Output format details below.

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \le N \le 20,\; 0 \le M \le \frac{N(N-1)}{2})\) --- the number of vertices and edges respectively.

Each of the next \(M\) lines contains two integers \(u\) and \(v\) \((0 \le u, v \le N-1, \; u \neq v)\) representing an undirected edge between vertices \(u\) and \(v\). There is at most one edge between any pair of vertices.

The graph is guaranteed to be simple and undirected.

outputFormat

Output a single line: YES if the given part can be produced by the Part Assembly Machine, and NO otherwise.

sample

1 0

YES