<PREV Problem:
NEXT>
Solved by 15 users: Mirzakhmet, fboy123, Zhukov_Dmitry, wInuX, WsemirZ, zloy_mipt, mazahaka, defrager, yiuyuho, murphy, Dest, LiuChenheng, dragonic, avi2011class, rayaryabinina.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Graph Planarity

Time limit = 30 second(s)

Graph with V < 3000 vertices and E < 10000 edges. i-th edge connects vertices si and ei (0 ≤ si, ei < V).

Input. Graph description:

V E
s1 e1
s2 e2
s3 e2
...
sE eE
Where V is number of vertise, E is number of edges, (s1, eE) — i-th edge description.

Output. 'YES' if the graph is planar, and 'NO' otherwise.

Input#1
2 1
0 1

Output#1
YES


Input#2
6 9
0 3
0 4
0 5
1 3
1 4
1 5
2 3
2 4
2 5
Output#2
NO

Author:
Classic problem, tests and description by Egor Cvetkov
19 Apr 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75