------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------ 

The structure of the company ShareChat can be described by a simple graph (without multiedges and self-loops) with $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. Each vertex of this graph is part of at most one simple cycle.

For each edge, you should find the number of simple paths that contain this edge and only contain at most one edge which belongs to a cycle.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $u$ and $v$, denoting the vertices connected by edge $i$.

------  Output ------
For each test case, print $M$ lines. For each $i$ ($1 ≤ i ≤ M$), the $i$-th of these lines should contain a single integer — the number of paths for edge $i$.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
the sum of $N+M$ for all test cases does not exceed $5 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (20 points):
the sum of answers for all edges in all test cases is smaller than $150 \cdot 10^{6}$
the sum of $N+M$ for all test cases does not exceed $5 \cdot 10^{5}$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
7 7
1 2
2 3
3 4
2 5
3 5
5 6
6 7
3 3
1 2
2 3
3 1
----- Sample Output 1 ------ 
6
4
6
6
6
10
6
1
1
1

Difficulty: VERY_HARD
Tags: Tree algorithms

Data structures

Graph algorithms

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
from collections import defaultdict as dd, deque
import sys
input = sys.stdin.readline

def cycle_part(C, n):
	P = [-1] * n
	root = 0
	Q = [(root, root)]
	O = [None] * n
	depth = 0
	cycs = []
	while Q:
		(u, par) = Q.pop()
		if P[u] != -1:
			if O[u] < O[par] and P[par] != u:
				cycs.append((par, u))
			continue
		P[u] = par
		O[u] = depth
		depth += 1
		for v in C[u]:
			if v != par:
				Q.append((v, u))
	which_cyc = dd(lambda : -1)
	cycles = []
	for (fro, to) in cycs:
		v = fro
		ix = len(cycles)
		cycle = [fro]
		which_cyc[fro] = ix
		while v != to:
			v = P[v]
			which_cyc[v] = ix
			cycle.append(v)
		cycles.append(cycle)
	return (cycles, which_cyc, P, O)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	C = [[] for _ in range(n)]
	E = []
	for _ in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		C[a].append(b)
		C[b].append(a)
		E.append((a, b))
	(cycles, which_cyc, P, O) = cycle_part(C, n)
	C_cyc = [[] for _ in range(n)]
	E_cyc = []
	for cycle in cycles:
		for i in range(len(cycle)):
			j = (i + 1) % len(cycle)
			a = cycle[i]
			b = cycle[j]
			C_cyc[a].append(b)
			C_cyc[b].append(a)
			C[a].remove(b)
			C[b].remove(a)
	V = {i for i in range(n) if C[i]}
	Pt = [-1] * n
	Ot = []
	for root in V:
		Q = [(root, root)]
		while Q:
			(v, par) = Q.pop()
			if Pt[v] != -1:
				continue
			Pt[v] = par
			Ot.append(v)
			for u in C[v]:
				Q.append((u, v))
	ways_down = [0] * n
	for v in reversed(Ot):
		if Pt[v] != v:
			ways_down[Pt[v]] += ways_down[v] + 1
	ways_up = [0] * n
	for v in Ot:
		ways_up[v] = ways_up[Pt[v]] + ways_down[Pt[v]] - 1 - ways_down[v] + 1
	ways_down2 = [0] * n
	for cycle in cycles:
		for i in range(len(cycle)):
			a = cycle[i]
			b = cycle[i - 1]
			ways_down2[a] += ways_down[b] + ways_up[b] + 1
			ways_down2[b] += ways_down[a] + ways_up[a] + 1
	for v in reversed(Ot):
		if Pt[v] != v:
			ways_down2[Pt[v]] += ways_down2[v] + 1
	ways_up2 = [0] * n
	for v in Ot:
		ways_up2[v] = ways_up2[Pt[v]] + ways_down2[Pt[v]] - 1 - ways_down2[v] + 1
	res = [-1] * m
	for i in range(m):
		(a, b) = E[i]
		if which_cyc[a] == which_cyc[b] != -1:
			prod = 1
			if a in V:
				prod *= ways_down[a] + ways_up[a] + 1
			if b in V:
				prod *= ways_down[b] + ways_up[b] + 1
			res[i] = prod
		else:
			if Pt[a] == b:
				parent = b
				child = a
			else:
				parent = a
				child = b
			res[i] = (1 + ways_down2[child]) * ways_up[child] + (1 + ways_down[child]) * ways_up2[child] - (1 + ways_down[child]) * ways_up[child]
	print(*res, sep='\n')