Lucky Edge

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
In an undirected unweighted graph, an edge of the graph is said to be lucky if it is a part of some cycle of the graph.
You are given a list E of M edges. We define f(i) as the number of intervals [l, r] (1 ≤ l ≤ i ≤ r ≤ M) such that if you build a graph from edges E_{l}, E_{l+1}, ..., E_{r}, the edge E_{i} will be a lucky edge in this graph.
Your task is to calculate the values of f(1), f(2), ..., f(M).
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer M denoting the number of edges.
Each of the next M lines contains two spaceseparated integers u_{i} and v_{i} denoting that ith edge connects nodes u_{i} and v_{i}.
Output
For each test case, output a single line containing M integers, ith of which should be value of f(i).
Constraints
 1 ≤ T ≤ 50
 1 ≤ M ≤ 5,000
 1 ≤ sum of M over all testcases ≤ 20,000
 1 ≤ u_{i}, v_{i} ≤ 10,000
 u_{i} ≠ v_{i}
Subtasks
 Subtask #1 (10 points): M ≤ 200 and sum of M ≤ 2,300
 Subtask #2 (20 points): M ≤ 1,000 and sum of M ≤ 4,000
 Subtask #3 (70 points): Original constraints
Example
Input: 2 3 1 2 3 4 2 1 5 1 2 2 3 3 4 1 4 4 2 Output: 1 0 1 2 3 3 2 2
Author:  fudail 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/LKYEDGE 
Tags  dfs, fudail, hard, oct17, treedp 
Date Added:  3102017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 