Tối thiểu hóa cạnh

Bessie có một đồ thị vô hướng liên thông $G$ gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cạnh. Đồ thị có thể chứa khuyên (cạnh nối một đỉnh với chính nó) nhưng không có cạnh song song.

Định nghĩa hàm $f_G(a,b)$ trả về giá trị đúng nếu tồn tại đường đi từ đỉnh $1$ đến đỉnh $a$ sử dụng đúng $b$ cạnh (mỗi cạnh có thể được đi qua nhiều lần).

Elsie cần xây dựng đồ thị $G^{\prime }$ sao cho $f_{G^{\prime }}(a,b)=f_G(a,b)$ với mọi giá trị $a$ và $b$, đồng thời tối thiểu hóa số cạnh của $G^{\prime }$.

Dữ liệu vào

Dòng đầu tiên chứa $T$ - số lượng bộ test.

Mỗi bộ test có dạng:

• Dòng đầu: hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x\le y\le N$) mô tả một cạnh nối đỉnh $x$ và đỉnh $y$.

Dữ liệu ra

Với mỗi bộ test, in ra số cạnh tối thiểu có thể có của $G^{\prime }$ trên một dòng.

Ràng buộc

• $1\le T\le 5·{10}^4$
• $2\le N\le {10}^5$
• $N-1\le M\le \frac{N(N+1)}{2}$
• Tổng $N$ trên tất cả các bộ test $\le {10}^5$
• Tổng $M$ trên tất cả các bộ test $\le 2·{10}^5$

Ví dụ

Ghi chú

Lưu ý rằng $G^{\prime }$ cũng là đồ thị vô hướng gồm $N$ đỉnh, có thể chứa khuyên và không có cạnh song song, nhưng không nhất thiết phải liên thông hay là đồ thị con của $G$.