Đồ Thị Khép Kín

Input chứa nhiều đồ thị vô hướng. Một đồ thị được gọi là khép kín theo cạnh nếu tồn tại một chu trình đi qua mỗi cạnh đúng một lần. Trong bài này toàn bộ $n$ đỉnh phải thuộc cùng một thành phần liên thông; vì vậy một đỉnh cô lập cũng khiến đồ thị không đạt yêu cầu.

Input

• Input gồm nhiều bộ dữ liệu. Mỗi bộ bắt đầu bằng hai số nguyên dương $n$ và $m$, sau đó là $m$ dòng cạnh.
• Dòng chỉ chứa số $0$ đánh dấu hết input; dòng này không tạo ra output.

Output

• Với mỗi bộ dữ liệu, in $1$ nếu đồ thị có chu trình Euler; ngược lại in $0$.

Constraints

• Mỗi bộ có $2\le n\le \text{999}$.
• Mỗi bộ có $1\le m\le 2\cdot 10^5$ trong package này.
• Các đỉnh được đánh số từ $1$ đến $n$.
• Sau bộ cuối là một dòng chỉ chứa $0$.

Scoring

• Subtask $1$ ($50\%$ số điểm): Trong mỗi bộ, $n\le 10$ và $m\le 14$; toàn input có không quá $3$ bộ.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

1
0