Bobo має зв'язний неорієнтований граф $G$ із $n$ вершинами та $m$ ребрами, вершини якого для зручності пронумеровано числами $1,2,\ldots,n$.

Bobo вибирає непорожню підмножину ребер так, щоб граф із вибраними ребрами залишався зв'язним. Він хоче дізнатися кількість таких підмножин за модулем $2$.

Зверніть увагу: граф є зв'язним, якщо для будь-яких двох вершин $a$ та $b$ існує шлях, який з'єднує $a$ та $b$.

Вхідні дані

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

Перший рядок містить два цілі числа $n$ та $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

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

Гарантується, що сума всіх $m$ не перевищує $2 \cdot 10^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