Ancient Greek isomorphism#9067

Ancient Greek isomorphism

1 second
128 megabytes
Easy

It is well known that the favourite graph of Zeus is a grid (namely, a rectangular grid graph) n \cdot m, i.e. an undirected graph of n \cdot m vertices and n \cdot (m - 1) + (n - 1) \cdot m edges, which can be represented as a grid with rows and columns so that each vertex is connected to neighbouring vertices.

Denote by the vertex at the intersection of the -th row and -th column. Formally, in the graph there are edges between and (i + 1, j) for all 1 \leq i < n, 1 \leq j \leq m, and edges between and (i, j + 1) for all 1 \leq i \leq n, 1 \leq j < m.

![Grid graph example](https://static.e-olymp.com/content/1e/1e5873e698fb27b41edca135ee78162cffe1ba84.gif)

(The illustration shows an example of a grid graph 6 \cdot 5)

And surprisingly, it turned out that the beloved graph of Poseidon is also non-oriented, it also contains n \cdot m vertices and n \cdot (m - 1) + (n - 1) \cdot m edges, and also does not contain loops and multiple edges. The vertices of his graph are numbered with integers from to n \cdot m.

Poseidon became interested, but maybe his and Zeus' graph are exactly the same (isomorphic)?

Formally, he wondered if its possible to find a unique correspondence between the vertices of the Poseidon graph and the vertices of the Zeus graph (that is, each vertex of the Poseidon graph should be associated with exactly one vertex of the Zeus graph so that each vertex of the Zeus graph was mapped to exactly one vertex of the Poseidon graph) so that two vertices are adjacent in one of these graphs if and only if their corresponding vertices are adjacent in another graph.

Help Poseidon with his difficult task, check his graph and the graph of Zeus for isomorphism!

Input

First line contains two integers and (2 \leq n, m, n \cdot m \leq 2 \cdot 10^5), indicating the size of the grid.

In the next n \cdot (m - 1) + (n - 1) \cdot m lines the description of the edges Poseidon's graph is given. The -th line contains two integers u_i and v_i (1 \leq u_i, v_i \leq n \cdot m, u_i \neq v_i), denoting an edge connecting the corresponding vertices.

It is guaranteed that the Poseidon's graph does not contain multiple edges.

Output

If the graphs of Poseidon and Zeus are isomorphic, print "**Yes**". Otherwise, print "**No**".

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

The graph from the second example is shown in the picture:

![Graph from example 2](https://static.e-olymp.com/content/bd/bdac6ad63d721c7db8b68b7af4f4e171c0aa0fdd.gif)