Centre for Gifted Education - Hanoi university of Technology

Cho đơn đồ thị vô hướng G = (V, E). G được gọi là cây nếu như G liên thông và giữa 2 đỉnh bất kì thuộc G có duy nhất 1 đường đi.

Chiều cao của cây là đường đi dài nhất từ gốc đến 1 đỉnh thuộc G.

Yêu cầu:

Cho đơn đồ thị vô hướng G = (V, E). Hãy kiểm tra xem G có phải là cây không. Nếu G là cây, tìm chiều cao của cây. Chọn gốc là đỉnh 1.

Input

Dòng 1: Chứa hai số n, m .

M dòng tiếp theo: Dòng thứ i có dạng 2 số nguyên u, v. Trong đó u, v là chỉ số hai đỉnh đầu mút của cạnh thứ i .

Output

Dòng 1: Ghi ra 1/0 tương ứng G là cây/không phải là cây.

Nếu G là cây dòng 2 ghi ra chiều cao của cây.

Example

Input:
4 3
1 2
1 3
2 4

Output:
1
3

Giới hạn:
1 <= n <= 100
1 <= m <= n(n-1)/2