Tom dự định đi dạo quanh thành phố, cậu đánh dấu trên bản đồ nhà của mình số \(0\) và những khu định tới các số tự nhiên khác rồi tìm các đường có độ dài bằng nhau giữa các khu. Các khu đều có thể đến được từ nhà của Tom.

Tom muốn đi qua ít nhất hai khu (không tính nhà mình) mà không quay lại khu nào, đồng thời cậu muốn tìm đường ngắn nhất để trở về nhà. Là sinh viên ngành công nghệ thông tin, Tom đã tự lập trình được thuật toán xác định hướng đi dạo. Do muốn đi bộ nhiều hơn, trong trường hợp không có đường vòng thuật toán của cậu sẽ nối hai khu sao cho độ dài của đường vòng ngắn nhất là lớn nhất.

Bạn hãy viết chương trình tính độ dài của đường vòng mà thuật toán của Tom tìm được.

Đầu vào

Dòng đầu tiên chứa số nguyên \(t\), số trường hợp kiểm thử.

Mỗi trường hợp kiểm thử được mô tả như sau:

• Dòng thứ nhất chứa số hai số nguyên \(m, n\) \((3 \le m, n \le 10^6)\), cho biết có \(m\) khu (bao gồm cả nhà Tom) và \(n\) đường nối giữa các khu.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((0 \le u, v\le m - 1)\) cho biết có đường đi từ khu \(u\) tới khu \(v\) và ngược lại.
• Một dòng trống ở cuối.

Các đường đi giữa hai khu (tính cả đường đi được thêm vào) được coi là có độ dài như nhau.

Đầu ra

\(t\) dòng, mỗi dòng chứa một số nguyên duy nhất.

Subtask

\(30\%\) số test có \(t = 1, 3 \le n, m \le 2000\).

\(70\%\) số test còn lại có \(t*max(m, n) \le 10^6\).

Ví dụ

Đầu vào:

2
7 8
0 1
0 2
1 3
3 4
0 4
2 5
2 6
0 6

5 4
0 1
1 3
0 2
2 4

Đầu ra:

3
5

Giải thích:

• Trong trường hợp kiểm thử đầu tiên, Tom đi theo đường \(0 \to 2 \to 6 \to 0\) là ngắn nhất.
• Trong trường hợp kiểm thử tiếp theo, không có đường vòng thỏa mãn điều kiện của Tom, thuật toán nối khu \(3\) với khu \(4\) khiến Tom phải đi theo đường \(0 \to 1 \to 3 \to 4 \to 2 \to 0\).