Bobo có một đồ thị vô hướng liên thông $G$ với $n$ đỉnh và $m$ cạnh, trong đó các đỉnh được đánh nhãn thuận tiện là $1,2,\ldots,n$.

Bobo chọn một tập con không rỗng gồm các cạnh sao cho đồ thị với các cạnh được chọn vẫn liên thông. Cậu muốn biết số tập con như vậy lấy modulo $2$.

Lưu ý rằng một đồ thị là liên thông nếu với hai đỉnh $a$ và $b$ bất kỳ, tồn tại một đường đi nối $a$ và $b$.

Dữ liệu vào

Dữ liệu vào chứa không hoặc nhiều bộ kiểm thử và kết thúc ở cuối tệp. Với mỗi bộ kiểm thử:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($2\le n\le2\cdot10^5$, $1\le m\le2\cdot10^5$).

Dòng thứ $i$ trong $m$ dòng tiếp theo chứa hai số nguyên $a_i$ và $b_i$, biểu thị một cạnh nối hai đỉnh $a_i$ và $b_i$.

Đảm bảo rằng tổng tất cả các giá trị $m$ không vượt quá $2\cdot10^5$ và tất cả các đồ thị đã cho đều liên thông.

Dữ liệu ra

Với mỗi bộ kiểm thử, in ra một số nguyên biểu thị số dư khi chia cho $2$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
1
0