All submissions for this problem are available.
Alice is the queen of ChefLand. She has initiated a road reform recently. The reform will last for M days.
Initially, there are N towns and no roads in ChefLand. Every day one bidirectional road will be built. On the i-th day, the road connecting the towns Ai and Bi will be built.
Nevertheless, Alice worries that if there is a road that will occur in every route from the town A to the town B for some pair of towns A and B, criminals might attack everyone who is traveling from the town A to the town B (or vice versa) for sure. So she calls such an unordered pair (A, B) unsafe.
You are given a plan of the road reform. Please, output the number of unsafe unordered pairs of towns, after each of M days.
The first line of input consists of the numbers N and M - the number of towns and the number of days.
The following M lines will describe the road reform. The i-th line will contain two integers X Y. That means that the bidirectional road, connecting the towns X and Y will be built during the i-th day.
Output M lines. The i-th line should contain the number of unsafe pairs of towns after the i-th day.
Input: 10 10 6 7 1 10 8 4 9 7 10 4 5 7 1 3 5 2 6 1 8 6 Output: 1 2 3 5 9 12 16 20 45 35
Subtask 1 (22 points): 1 <= N <= 5, 1 <= M <= 5.
Subtask 2 (13 points): 1 <= N <= 100, 1 <= M <= 100.
Subtask 3 (20 points): 1 <= N <= 5000, 1 <= M <= 5000.
Subtask 4 (45 points): 1 <= N <= 5*105, 1 <= M <= 5*105.
|Tags||dynamic-bcc, ltime03, medium-hard, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.