Planarity P20463


Statement
 

pdf   zip

html

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 uv) 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