
Safe Routes
|
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.
Input
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
Output M lines. The i-th line should contain the number of unsafe pairs of towns after the i-th day.
Example
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
Scoring
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.
Author: | xcwgf666 |
Tester: | rubanenko |
Editorial | http://discuss.codechef.com/problems/ROUTES |
Tags | dynamic-bcc, ltime03, medium-hard, xcwgf666 |
Date Added: | 22-07-2013 |
Time Limit: | 1 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS |
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. |
