[Graph]. Kiểm tra chu trình trên đồ thị vô hướng.

Cho đồ thị vô hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy xác định xem đồ thị có tồn tại chu trình hay không? Bài này các bạn cài đặt bằng 3 phương pháp : DFS, BFS và DSU.

Input Format

Dòng đầu tiên là 2 số n, m, tương ứng với số lượng đỉnh, cạnh của đồ thị. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. (1<=n<=1000; 1<=m<=n*(n-1)/2)

Constraints

.

Output Format

In ra 1 nếu đồ thị tồn tại chu trình, ngược lại in ra 0.

Ví dụ:

Dữ liệu vào

5 6
1 2
1 3
1 4
2 5
3 4
3 5

Dữ liệu ra

1