У Bobo есть связный неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами. Для удобства вершины пронумерованы числами $1,2,\ldots,n$.

Bobo выбирает непустое подмножество рёбер так, чтобы граф с выбранными рёбрами оставался связным. Он хочет узнать количество таких подмножеств по модулю $2$.

Напомним, что граф называется связным, если для любых двух вершин $a$ и $b$ существует путь, соединяющий $a$ и $b$.

Входные данные

Входные данные содержат ноль или более тестов и завершаются концом файла. Для каждого теста:

Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 2\cdot10^5$, $1 \le m \le 2\cdot10^5$).

В $i$-й из следующих $m$ строк содержатся два целых числа $a_i$ и $b_i$, обозначающих ребро между вершинами $a_i$ и $b_i$.

Гарантируется, что сумма всех $m$ не превосходит $2\cdot10^5$ и все заданные графы связны.

Выходные данные

Для каждого теста выведите целое число — остаток по модулю $2$.

Примеры

Входные данные 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

Выходные данные 1

1
1
0