Bobo memiliki sebuah graf tak berarah terhubung $G$ dengan $n$ simpul dan $m$ sisi, yang simpul-simpulnya diberi nomor $1,2,\ldots,n$ agar mudah dirujuk.

Bobo memilih suatu himpunan bagian sisi yang tidak kosong sedemikian sehingga graf dengan sisi-sisi yang dipilih tetap terhubung. Ia ingin mengetahui banyaknya himpunan bagian seperti itu modulo $2$.

Perhatikan bahwa sebuah graf disebut terhubung jika, untuk sembarang dua simpul $a$ dan $b$, terdapat sebuah jalur yang menghubungkan $a$ dan $b$.

Masukan

Masukan berisi nol atau lebih kasus uji dan diakhiri oleh akhir berkas. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

Baris ke-$i$ dari $m$ baris berikutnya berisi dua bilangan bulat $a_i$ dan $b_i$ yang menyatakan sebuah sisi antara simpul $a_i$ dan $b_i$.

Dijamin bahwa jumlah seluruh $m$ tidak melebihi $2 \cdot 10^5$, dan semua graf yang diberikan terhubung.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat yang menyatakan sisa pembagian modulo $2$.

Contoh

Masukan 1

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

Keluaran 1

1
1
0