Language: C++

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[](auto f,auto... args){return f(f,args...);};

int cnt=0,cnt2=0;
template<typename T>
class dinamic_connectivity{
    using DC=dinamic_connectivity*;
	class euler_tour_tree{
		public:
		struct node;
		using np=node*;
		using lint=long long;
		struct node{
			np ch[2]={nullptr,nullptr};
			np p=nullptr;
			int l,r,sz;
			T val=et,sum=et;
			bool exact=1;
			node(){}
			node(int l,int r):l(l),r(r),sz(l==r){}
			bool is_root() {
				return !p;
			}
		};
		vector<hash_map<int,np>>ptr;
		np get_node(int l,int r){
			if(ptr[l].find(r)==ptr[l].end())ptr[l][r]=new node(l,r);
			return ptr[l][r];
		}
		np root(np t){
			if(!t)return t;
			while(t->p)t=t->p;
			return t;
		}
		bool same(np s,np t){
			return root(s)==root(t);
		}
		np reroot(np t){
			auto s=split(t);
			return merge(s.second,s.first);
		}
		pair<np,np> split(np s){
			splay(s);
			np t=s->ch[0];
			if(t)t->p=nullptr;
			s->ch[0]=nullptr;
			return {t,update(s)};
		}
		pair<np,np> split2(np s){
			splay(s);
			np t=s->ch[0];
			np u=s->ch[1];
			if(t)t->p=nullptr;
			s->ch[0]=nullptr;
			if(u)u->p=nullptr;
			s->ch[1]=nullptr;
			return {t,u};
		}
		tuple<np,np,np> split(np s,np t){
			auto u=split2(s);
			if(same(u.first,t)){
				auto r=split2(t);
				return make_tuple(r.first,r.second,u.second);
			}else{
				auto r=split2(t);
				return make_tuple(u.first,r.first,r.second);
			}
		}
		template<typename First, typename... Rest>
		np merge(First s,Rest... t){
			return merge(s,merge(t...));
		}
		np merge(np s,np t){
			if(!s)return t;
			if(!t)return s;
			while(s->ch[1])s=s->ch[1];
			splay(s);
			s->ch[1]=t;
			if(t)t->p=s;
			return update(s);
		}
		int size(np t){return t?t->sz:0;}
		np update(np t){
			t->sum=et;
			if(t->ch[0])t->sum=fn(t->sum,t->ch[0]->sum);
			if(t->l==t->r)t->sum=fn(t->sum,t->val);
			if(t->ch[1])t->sum=fn(t->sum,t->ch[1]->sum);
			t->sz=size(t->ch[0])+(t->l==t->r)+size(t->ch[1]);
			return t;
		}
		void push(np t){
			//遅延評価予定
		}
		void rot(np t,bool b){
			np x=t->p,y=x->p;
			if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
			t->ch[b]=x,x->p=t;
			update(x);update(t);
			if((t->p=y)){
				if(y->ch[0]==x)y->ch[0]=t;
				if(y->ch[1]==x)y->ch[1]=t;
				update(y);
			}
		}
		void splay(np t){
			push(t);
			while(!t->is_root()){
				np q=t->p;
				if(q->is_root()){
					push(q), push(t);
					rot(t,q->ch[0]==t);
				}else{
					np r=q->p;
					push(r), push(q), push(t);
					bool b=r->ch[0]==q;
					if(q->ch[1-b]==t)rot(q,b),rot(t,b);
					else rot(t,1-b),rot(t,b);
				}
			}
		}
		void debug(np t){
			if(!t)return;
			debug(t->ch[0]);
			cerr<<t->l<<"-"<<t->r<<" ";
			debug(t->ch[1]);
		}
		constexpr static T et={};
		constexpr static T fn(T s,T t){
			return s;
		}
		public:
		euler_tour_tree(){}
		euler_tour_tree(int sz){
			ptr.resize(sz);
			for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
		}
		int size(int s){
			np t=get_node(s,s);
			splay(t);
			return t->sz;
		}
		bool same(int s,int t){
            return root(get_node(s,s))==root(get_node(t,t));
        }
		void set_size(int sz){
			ptr.resize(sz);
			for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
		}
		void update(int s,T x){
			np t=get_node(s,s);
			splay(t);
			t->val=fn(t->val,x);
			update(t);
		}
		auto get(int s){
			np t=get_node(s,s);
			splay(t);
			vector<int>res1;
            vector<pair<int,int>>res2;
			stack<np>stk;
			stk.emplace(t);
			function<void(np)>dfs=[&](np t){
				cnt++;
				if(!t)continue;
				if(t->l==t->r)res1.emplace_back(t->l);
                if(t->l<t->r&&t->exact){
					res2.emplace_back(t->l,t->r);
					t->exact=0;
				}
				dfs(t->ch[0]);
				dfs(t->ch[1]);
				upadte(t);
			}
			return make_pair(res1,res2);
		}
		bool link(int l,int r){
			if(same(l,r))return 0;
			merge(reroot(get_node(l,l)),get_node(l,r),reroot(get_node(r,r)),get_node(r,l));
			return 1;
		}
		bool cut(int l,int r){
			if(ptr[l].find(r)==ptr[l].end())return 0;
			np s,t,u;
			tie(s,t,u)=split(get_node(l,r),get_node(r,l));
			merge(s,u);
			np p=ptr[l][r];
			np q=ptr[r][l];
			ptr[l].erase(r);
			ptr[r].erase(l);
			delete p;delete q;
			return 1;
		}
		T get_sum(int p,int v){
			cut(p,v);
			np t=get_node(v,v);
			splay(t);
			T res=t->sum;
			link(p,v);
			return res;
		}
	};
	int dep=1;
	vector<euler_tour_tree> ett;
	vector<vector<unordered_set<int>>>edges;
	int sz;
	public:
	dinamic_connectivity(int sz):sz(sz){
		ett.emplace_back(sz);
		edges.emplace_back(sz);
	}
	bool link(int s,int t){
		if(s==t)return 0;
		if(ett[0].link(s,t))return 1;
		edges[0][s].insert(t);
		edges[0][t].insert(s);
		return 0;
	}
	bool same(int s,int t){
		return ett[0].same(s,t);
	}
	int size(int s){
		return ett[0].size(s);
	}
	vector<int>get_vertex(int s){
		return ett[0].vertex_list(s);
	}
	bool cut(int s,int t){
		if(s==t)return 0;
		for(int i=0;i<dep;i++){
			edges[i][s].erase(t);
			edges[i][t].erase(s);
		}
		for(int i=dep-1;i>=0;i--){
			if(ett[i].cut(s,t)){
				if(dep-1==i){
					dep++;
					ett.emplace_back(sz);
					edges.emplace_back(sz);
				}
				return !try_reconnect(s,t,i);
			}
		}
		return 0;
	}
	bool try_reconnect(int s,int t,int k){
		for(int i=0;i<k;i++){
			ett[i].cut(s,t);
		}
		for(int i=k;i>=0;i--){
			if(ett[i].size(s)>ett[i].size(t))swap(s,t);
			vector<pair<int,int>> edge_list;
            vector<int> vs;
            tie(vs,edge_list)=ett[i].get(s);
			for(auto e:edge_list){
				if(ett[i+1].link(e.first,e.second))cnt2++;
			}
			for(auto x:vs)for(auto itr=edges[i][x].begin();itr!=edges[i][x].end();){
				auto y=*itr;
				itr=edges[i][x].erase(itr);
				edges[i][y].erase(x);
				if(ett[i].same(x,y)){
					edges[i+1][x].insert(y);
					edges[i+1][y].insert(x);
				}else{
					for(int j=0;j<=i;j++){
						ett[j].link(x,y);
					}
					return 1;
				}
			}
		}
		return 0;
	}
};
 
int main(){
	lint n,m;
	cin>>n>>m;
	dinamic_connectivity<tuple<>>dc(n);
	vec s(m),t(m);
	rep(i,m){
		cin>>s[i]>>t[i];
		s[i]--;t[i]--;
		dc.link(s[i],t[i]);
	}
	lint ans=0;
	rep(i,m){
		if(dc.cut(s[i],t[i])){
			ans+=lint(dc.size(s[i]))*lint(dc.size(t[i]));
		}
		cout<<ans<<endl;
	}
}


Compiler output:
a.cc:51:19: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   51 | inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
      |                   ^~~~
a.cc:51:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   51 | inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
      |                                 ^~~~
a.cc:52:19: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   52 | inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
      |                   ^~~~
a.cc:52:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   52 | inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
      |                                 ^~~~
a.cc: In lambda function:
a.cc:218:39: error: continue statement not within a loop
  218 |                                 if(!t)continue;
      |                                       ^~~~~~~~
a.cc: In member function 'auto dinamic_connectivity<T>::euler_tour_tree::get(int)':
a.cc:228:25: error: expected ',' or ';' before 'return'
  228 |                         return make_pair(res1,res2);
      |                         ^~~~~~
a.cc: In instantiation of 'auto dinamic_connectivity<T>::euler_tour_tree::get(int) [with T = std::tuple<>]':
a.cc:307:41:   required from 'bool dinamic_connectivity<T>::try_reconnect(int, int, int) [with T = std::tuple<>]'
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |                               ~~~~~~~~~~^~~
a.cc:294:13:   required from 'bool dinamic_connectivity<T>::cut(int, int) [with T = std::tuple<>]'
  294 |                                 return !try_reconnect(s,t,i);
      |                                         ^~~~~~~~~~~~~
a.cc:342:12:   required from here
  342 |                 if(dc.cut(s[i],t[i])){
      |                    ~~~~~~^~~~~~~~~~~
a.cc:226:39: error: 'upadte' was not declared in this scope; did you mean 'update'?
  226 |                                 upadte(t);
      |                                 ~~~~~~^~~
      |                                 update
a.cc: In instantiation of 'bool dinamic_connectivity<T>::try_reconnect(int, int, int) [with T = std::tuple<>]':
a.cc:294:13:   required from 'bool dinamic_connectivity<T>::cut(int, int) [with T = std::tuple<>]'
  294 |                                 return !try_reconnect(s,t,i);
      |                                         ^~~~~~~~~~~~~
a.cc:342:12:   required from here
  342 |                 if(dc.cut(s[i],t[i])){
      |                    ~~~~~~^~~~~~~~~~~
a.cc:307:30: error: no match for 'operator=' (operand types are 'std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>' and 'void')
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:5:
/usr/include/c++/14/tuple:2355:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::tuple<_U1, _U2>&) [with _U2 = _U1; _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&]'
 2355 |         operator=(const tuple<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2355:9: note:   template argument deduction/substitution failed:
a.cc:307:30: note:   mismatched types 'const std::tuple<_T1, _T2>' and 'void'
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/tuple:2365:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::tuple<_U1, _U2>&&) [with _U2 = _U1; _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&]'
 2365 |         operator=(tuple<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2365:9: note:   template argument deduction/substitution failed:
a.cc:307:30: note:   mismatched types 'std::tuple<_T1, _T2>' and 'void'
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/tuple:2375:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&]'
 2375 |         operator=(const pair<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2375:9: note:   template argument deduction/substitution failed:
a.cc:307:30: note:   mismatched types 'const std::pair<_T1, _T2>' and 'void'
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/tuple:2386:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&]'
 2386 |         operator=(pair<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2386:9: note:   template argument deduction/substitution failed:
a.cc:307:30: note:   mismatched types 'std::pair<_T1, _T2>' and 'void'
  307 |             tie(vs,edge_list)=ett[i].get(s);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/tuple:2332:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&>) [with _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&; std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&> = const std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&]'
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2334:52: note:   no known conversion for argument 1 from 'void' to 'std::__conditional_t<true, const std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&, const std::__nonesuch&>' {aka 'const std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&'}
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2333 |                                 const tuple&,
      |                                 ~~~~~~~~~~~~~       
 2334 |                                 const __nonesuch&> __in)
      |                                 ~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/14/tuple:2343:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&>) [with _T1 = std::vector<int>&; _T2 = std::vector<std::pair<int, int> >&; std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&> = std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&&]'
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2345:47: note:   no known conversion for argument 1 from 'void' to 'std::__conditional_t<true, std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&&, std::__nonesuch&&>' {aka 'std::tuple<std::vector<int, std::allocator<int> >&, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&>&&'}
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2344 |                                 tuple&&,
      |                                 ~~~~~~~~       
 2345 |                                 __nonesuch&&> __in)
      |                                 ~~~~~~~~~~~~~~^~~~