Cho một đồ thị vô hướng không có khuyên và không có cạnh bội.

Hãy gán một giá trị nguyên không âm cho mỗi đỉnh của đồ thị. Một phép gán được gọi là hợp lệ nếu nó thỏa mãn hai điều kiện:

• hai đỉnh kề nhau bất kỳ có giá trị chênh lệch nhau đúng $1$;
• nếu giá trị của một đỉnh nhỏ hơn hẳn giá trị của tất cả các đỉnh kề với nó, thì giá trị đó bằng $0$.

Hãy tìm số lượng phép gán hợp lệ theo modulo $998\,244\,353$. Hai phép gán được coi là khác nhau nếu tồn tại một đỉnh có giá trị khác nhau trong hai phép gán đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ là số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): số lượng đỉnh và số lượng cạnh của đồ thị.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$): hai đầu mút của cạnh tương ứng. Đồ thị không chứa khuyên hoặc cạnh bội. Mọi đỉnh đều có ít nhất một đỉnh kề.

Tổng của $m$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.

Kết quả

Đối với mỗi bộ dữ liệu, hãy in ra một số nguyên: số lượng phép gán hợp lệ theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

2
4 3
1 2
2 3
3 4
3 3
1 2
2 3
1 3

Kết quả 1

6
0