A graph is called *planar* if it can be drawn in the plane without any
crossings. In a drawing of a graph, nodes are identified with points in the
plane, and edges with lines connecting the corresponding end nodes. No edge
is allowed to cross another edge or node in the drawing.

Write a program that determines whether a given undirected graph is planar or not.

**Input**

Input consists of zero or more test cases. Each test case consists of a graph.

A graph is given in the following way: First, a line contains two integers *n*
and *m*, where *n* denotes the number of vertices of the graph,
and *m* denotes its number of edges
(1 ≤ *n* ≤ 20 and 0≤ *m*). Then follow *m* lines, one for every edge
of the graph, each containing two integers *u* and *v* (with *u*≠ *v*) meaning
that the graph contains the edge {*u*,*v*}. Vertices in the graph are labelled
from 1 to *n*. There are not repeated edges.

**Output**

For each test case, print a line with the string `YES` if the graph is
planar or with the string `NO` otherwise.

Public test cases

**Input**

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

**Output**

NO YES

Information

- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++
- User solutions
- Event
- Segon Concurs de Programació de la UPC - Final
- Date
- 2004-09-29