Un grafo no dirigido (no necesariamente conexo) es bipartito si sus nodos se pueden dividir en dos conjuntos de modo que cada arista una un nodo de un conjunto con uno del otro. Decide si el grafo lo es.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\) y \(m\) \((0 \le m \le 2 \cdot 10^5)\). Cada una de las siguientes \(m\) líneas tiene una arista \(a\) \(b\) \((0 \le a, b < n, a \ne b)\). No hay aristas repetidas.

Salida

true si es bipartito y false si no.

Ejemplo 1

Entrada

4 5
0 1
0 2
0 3
1 2
2 3

Salida

false

Ejemplo 2

Entrada

4 4
0 1
1 2
2 3
3 0

Salida

true

Ejemplo 3

Entrada

3 0

Salida

true