Uniform Parity Matrix Buttons

Given an n × n grid that contains m buttons (each located at a unique cell), your task is to choose a non‐empty subset of these buttons to press so that the parity of the number of pressed buttons is the same in every row and every column.

In other words, if for every row i and every column j we denote by a_i and b_j the number (modulo 2) of pressed buttons in that row and column respectively, then you need to have:

[ \text{for all } i,, a_i = p \quad \text{and} \quad \text{for all } j,, b_j = p, ]

for some parity p (either 0 or 1). Note that p is common for all rows and columns. Determine if such a selection exists.

inputFormat

The first line contains two integers n and m where n is the dimension of the grid and m is the number of buttons.

Each of the following m lines contains two integers r and c (1-indexed) representing the row and column of a button.

outputFormat

Print YES if there exists a non-empty selection of buttons to press such that every row and column has the same parity of pressed buttons. Otherwise, print NO.

sample

2 3
1 1
1 2
2 1

YES