1986F - Non-academic Problem - CodeForces Solution

from sys import *
input=lambda:stdin.readline().rstrip()

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def out(l):
    print(' '.join(map(str,l)))

def yes():
    print('Yes')

def no():
    print('No')

def alice():
    print('Alice')

def bob():
    print('Bob')

def vis(a):
        if v_a[a-1]==1:
        return True
    else:
        return False

@bootstrap              
def dfs(a,cnt,par=0):
            temp=adj_list[a-1]
    v_a[a-1]=1
    min_step[a]=cnt
    for i,j in enumerate(temp):
        if j==par:
            continue
        if not vis(j):
            yield dfs(j,cnt+1,a)
            min_step[a]=min(min_step[j],min_step[a])
            sub[a]+=sub[j]
            if min_step[j]>cnt:
                bridge.append(j)
        else:
            min_step[a]=min(min_step[j],min_step[a])
    sub[a]+=1
    yield
        
def solve():
    global v,e,v_a,adj_list,min_step,sub,bridge
        v,e=map(int,input().split())
    v_a=[0]*v
    sub=[0]*(v+1)
    bridge=[]
    min_step=[0]*(v+1)
    ans=v*(v-1)//2
    adj_list=[[] for i in range(v)]
    for i in range(e):
        x,y=map(int,input().split())
        adj_list[x-1].append(y)
        adj_list[y-1].append(x)
    dfs(1,1,0)
    for i,j in enumerate(bridge):
        ans=min(ans,sub[j]*(sub[j]-1)//2+(v-sub[j])*(v-sub[j]-1)//2)
    print(ans)

for _ in range(int(input())):
    solve()