Planarity Test for Hamiltonian Graphs

An undirected graph \(G=(V,E)\) is called planar if it can be drawn on the plane in such a way that any two edges that do not share a vertex do not intersect. Testing whether a graph is planar is an important problem in graph theory.

In this problem, you are given a special graph which is guaranteed to have a Hamiltonian cycle (i.e. a cycle containing all vertices). The vertices on this cycle are given in a specific order, and you may assume that they are arranged on a circle in that order. The remaining edges of the graph (called chords) are added to this cycle.

Your task is to determine if the graph is planar. In other words, is it possible to assign each chord to be drawn either inside or outside the circle so that no two chords drawn on the same side cross each other? Two chords \((a,b)\) and \((c,d)\) (with \(a<b\) and \(c<d\)) cross if and only if either of the following conditions holds: \[ a < c < b < d \quad \text{or} \quad c < a < d < b. \]

If such an assignment exists (i.e. the intersection graph of the chords is bipartite), then the graph is planar; otherwise, it is not.

inputFormat

The input consists of multiple lines. The first line contains two integers \(n\) and \(m\) where \(n\) is the number of vertices and \(m\) is the total number of edges in the graph. The vertices are numbered from 1 to \(n\).

The second line contains a permutation of \(n\) integers representing the order of vertices in the Hamiltonian cycle. The cycle is formed by connecting the vertices in the given order and an edge between the last and the first vertex.

The next \(m - n\) lines each contain two integers \(u\) and \(v\) denoting an edge between vertices \(u\) and \(v\) that is not part of the Hamiltonian cycle (i.e. a chord). It is guaranteed that the given Hamiltonian cycle exists, and every edge not on the cycle is listed exactly once.

outputFormat

Output a single line: Yes if the graph is planar, and No otherwise.

sample

4 4
1 2 3 4

Yes