#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long Answer = 0;
namespace disjoint_set { // maintain disjoint set of components
int p[MAXN];
int component_size[MAXN];
void Init() {
iota(p, p + MAXN, 0);
fill(component_size, component_size + MAXN, 1);
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
}
namespace ingoing_edges {
map<int, set<int>> ingoing_edges_from_component[MAXN]; // set of ingoing edges from other components to component[] (a list oh them), thus number of edges = size() * component[].size()
int total_size_ingoing_edges_from_component[MAXN]; // number of all element of elements of ingoing_edges_from_component[]
void Insert(int base, int ingoing_component, int ingoing_id) {
assert(ingoing_component == disjoint_set::Find(ingoing_id));
if (ingoing_edges_from_component[base][ingoing_component].count(ingoing_id) == 0) {
total_size_ingoing_edges_from_component[base]++;
ingoing_edges_from_component[base][ingoing_component].emplace(ingoing_id);
}
}
void Delete(int base, int ingoing_component, int ingoing_id) {
assert(ingoing_component == disjoint_set::Find(ingoing_id));
if (ingoing_edges_from_component[base][ingoing_component].count(ingoing_id) == 1) {
total_size_ingoing_edges_from_component[base]--;
ingoing_edges_from_component[base][ingoing_component].erase(ingoing_id);
}
}
void Delete(int base, int ingoing_component) {
total_size_ingoing_edges_from_component[base] -= ingoing_edges_from_component[base][ingoing_component].size();
ingoing_edges_from_component[base].erase(ingoing_component);
}
}
namespace outgoing_edges {
map<int, int> edges_between_components[MAXN]; // count how many edges are there from component[] to another component divided by another component.size()
int total_size_outgoing_edges_to_component[MAXN]; // sum of all edges_between_component[]'s value
void Insert(int from, int to, int x) {
total_size_outgoing_edges_to_component[from] += x;
edges_between_components[from][to] += x;
}
void Delete(int from, int to, int x) {
total_size_outgoing_edges_to_component[from] -= x;
edges_between_components[from][to] -= x;
if (edges_between_components[from][to] == 0) {
edges_between_components[from].erase(to);
}
}
void Delete(int from, int to) {
total_size_outgoing_edges_to_component[from] -= edges_between_components[from][to];
edges_between_components[from].erase(to);
}
}
using ingoing_edges::ingoing_edges_from_component;
using ingoing_edges::total_size_ingoing_edges_from_component;
using outgoing_edges::edges_between_components;
using outgoing_edges::total_size_outgoing_edges_to_component;
bool IsThereAnEdgeBetweenComponent(int x, int y) {
return (edges_between_components[x].count(y) == 1);
}
long long ComponentAnswer(int sz) { // count number of edges in one component (a component is a complete directed graph)
return 1ll * sz * (sz - 1);
}
set<pair<int, int>> todo; // pending to use ConnectComponent(x, y)
void ConnectComponent(int x, int y) {
x = disjoint_set::Find(x);
y = disjoint_set::Find(y);
if (x == y) return;
int components_x_size = disjoint_set::component_size[x];
int components_y_size = disjoint_set::component_size[y];
{ // delete edges between components to be connected
Answer -= 1ll * edges_between_components[y][x] * components_x_size;
Answer -= 1ll * edges_between_components[x][y] * components_y_size;
outgoing_edges::Delete(x, y);
outgoing_edges::Delete(y, x);
ingoing_edges::Delete(x, y);
ingoing_edges::Delete(y, x);
}
{ // maintain weighted union heuristic and update disjoint set
int total_size_x = total_size_ingoing_edges_from_component[x] + total_size_outgoing_edges_to_component[x];
int total_size_y = total_size_ingoing_edges_from_component[y] + total_size_outgoing_edges_to_component[y];
if (total_size_x < total_size_y) {
swap(x, y); // this still is affected by the weighted union heuristic, thus the will take O(n log n) merges total
swap(components_x_size, components_y_size);
}
// Union in disjoint set
disjoint_set::p[y] = x;
disjoint_set::component_size[x] += disjoint_set::component_size[y];
disjoint_set::component_size[y] = 0;
}
{ // update answer for full component
Answer -= ComponentAnswer(components_x_size);
Answer -= ComponentAnswer(components_y_size);
Answer += ComponentAnswer(components_x_size + components_y_size);
}
{ // handle all merges of ingoing edge of x and y
Answer += 1ll * total_size_ingoing_edges_from_component[x] * components_y_size; // all vertices that can reach x can now reach y as well
Answer += 1ll * total_size_ingoing_edges_from_component[y] * components_x_size; // all vertices that can reach y can now reach x as well
while (!ingoing_edges_from_component[y].empty()) {
auto ingoing_edges_from_component_y_key_value_pair = begin(ingoing_edges_from_component[y]);
int current_ingoing_component = ingoing_edges_from_component_y_key_value_pair->first;
for (auto ¤t_ingoer : ingoing_edges_from_component_y_key_value_pair->second) {
if (ingoing_edges_from_component[x][current_ingoing_component].count(current_ingoer) == 1) {
outgoing_edges::Delete(current_ingoing_component, y, 1); // when merging edge_between_components[][x] and [][y], this will be double counted, so we subtract it
Answer -= components_x_size + components_y_size; // Answer is also double counted
} else {
ingoing_edges::Insert(x, current_ingoing_component, current_ingoer);
}
}
if (IsThereAnEdgeBetweenComponent(x, current_ingoing_component)) {
todo.emplace(x, current_ingoing_component);
}
outgoing_edges::Insert(current_ingoing_component, x, edges_between_components[current_ingoing_component][y]);
outgoing_edges::Delete(current_ingoing_component, y);
ingoing_edges::Delete(y, current_ingoing_component);
}
}
{ // handle all merges of outgoing edge of x and y
while (!edges_between_components[y].empty()) {
auto outgoing_edges_y_key_value_pair = begin(edges_between_components[y]);
int nxt_component = outgoing_edges_y_key_value_pair->first;
for (auto ¤t_ingoer : ingoing_edges_from_component[nxt_component][y]) {
ingoing_edges::Insert(nxt_component, x, current_ingoer);
}
if (IsThereAnEdgeBetweenComponent(nxt_component, x)) {
todo.emplace(x, nxt_component); // there is an edge from nxt_component to x and vice versa, so we need to merge them into one component
}
outgoing_edges::Insert(x, nxt_component, edges_between_components[y][nxt_component]);
outgoing_edges::Delete(y, nxt_component);
ingoing_edges::Delete(nxt_component, y);
}
}
}
void AddEdge(int x, int y) {
int real_x = x;
int real_y = y;
x = disjoint_set::Find(x);
y = disjoint_set::Find(y);
if (x == y) return;
if (IsThereAnEdgeBetweenComponent(y, x)) {
todo.emplace(x, y);
while (!todo.empty()) {
pair<int, int> cur = *begin(todo);
todo.erase(cur);
ConnectComponent(cur.first, cur.second);
}
} else if (ingoing_edges_from_component[y][x].count(real_x) == 0) { // if edge (real_x, real_y) doesn't already exist
outgoing_edges::Insert(x, y, 1);
ingoing_edges::Insert(y, x, real_x);
Answer += disjoint_set::component_size[y]; // there forms an edge from real_x to all nodes in component y
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
disjoint_set::Init();
int N, M;
cin >> N >> M;
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
AddEdge(--A, --B);
cout << Answer << '\n';
}
return 0;
}
