Số đường đi đơn

Cho một đồ thị vô hướng gồm $n$ đỉnh và $n$ cạnh. Đồ thị liên thông (từ một đỉnh bất kì có thể đi tới mọi đỉnh khác), không có khuyên và không có cạnh bội.

Hãy đếm số đường đi đơn có độ dài ít nhất $1$ trong đồ thị. Một đường đi là dãy đỉnh $v_1,v_2,\dots ,v_k$ sao cho mỗi cặp đỉnh liên tiếp được nối bởi một cạnh. Độ dài đường đi là số cạnh trong đó. Đường đi đơn là đường đi mà tất cả các đỉnh đôi một khác nhau. Hai đường đi chỉ khác nhau ở thứ tự duyệt (ví dụ $[1,2,3]$ và $[3,2,1]$) được coi là cùng một đường đi.

Bài toán có $t$ bộ dữ liệu độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 2·{10}^4$) — số bộ dữ liệu.
• Mỗi bộ dữ liệu bắt đầu bằng dòng chứa số nguyên $n$ ($3\le n\le 2·{10}^5$) — số đỉnh đồng thời cũng là số cạnh.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$) mô tả cạnh thứ $i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — số đường đi đơn có độ dài ít nhất $1$.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $3\le n\le 2·{10}^5$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.
• Đồ thị liên thông, không có khuyên, không có cạnh bội.

Ví dụ