1454E - Number of Simple Paths - CodeForces Solution

from collections import deque
import sys




def get_int():
    return int(sys.stdin.readline().strip())

def get_ints():
    return map(int,sys.stdin.readline().strip().split())

def get_list():
    return list(map(int,sys.stdin.readline().strip().split()))

def get_string():
    return sys.stdin.readline().strip()


def dfs(u,n):
        
    q = deque()
    visited.clear()

    for i in range(n):
        par[i] = -1
    found = False

    q.append(u)
    while q and (not found):
        node = q.pop()
        if (node in visited):
            continue
        visited.add(node)
        for u in adj[node]:
            if found:
                break
            if (u not in visited):
                par[u] = node
                q.append(u)
                            elif u!=par[node]:
                found=True
                while node!=u:
                    isOnCycle[node]=True
                    cycle.add(node)
                    node = par[node]
                isOnCycle[u] = True
                cycle.add(u)
                break

def subSize(u):
    
    
    val = 1
    for v in adj[u]:
        if (not isOnCycle[v]):
            val+=treeSize(v,u)

    return val


def treeSize(root,parent):
                q = deque()
    q.append(root)

    visited.clear()

    
    count= 1
    while q:
        node = q.popleft()
        if node in visited:
            continue
        visited.add(node)

        
        for u in adj[node]:
            if (u in visited) or u==parent:
                continue

                                    
            q.append(u)
            count+=1
                return count
    
    
for _ in range(get_int()):
    n = get_int()

    lim = n
    adj = [[] for _ in range(lim)]
    isOnCycle = [False]*lim
    cycle = set()
    visited = set()
    par = [-1]*lim
    sub = [-1]*lim
        


    

    for i in range(n):
        adj[i].clear()
        isOnCycle[i]=False
        sub[i] = -1
    cycle.clear()
    

    for _ in range(n):
        u,v = get_ints()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)

    



    dfs(0,n)

        ans = n*(n-1)

    for u in cycle:
       val=subSize(u)
       ans = ans - (val*(val-1)//2)
    print(ans)