#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = INT_MAX;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

inline int readint() { int in; scanf("%d", &in); return in; }
inline void printint(int out) { printf("%d\n", out); }
inline void printLL(LL out) { printf("%lld\n", out); }

//・わりと遅い…まあでもlog^2 nといわれればそんな感じではある
//・サンプリングとTest-Allっぽいものを導入してみたけどうまくいってるのかわからない…
//
//References
//・Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48.4 (2001): 723-760.
//・Thorup, Mikkel. "Near-optimal fully-dynamic graph connectivity." Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM, 2000.
class FullyDynamicConnectivity {
	//local search treeとglobalな構造は同じノードで表して、ternary search treeっぽくやる
	struct Node {
		Node *left, *right;	//local treeの子ノード
		Node *mid;			//所有するlocal treeの根
		Node *parent;		//local/global treeの親ノード
		int numLeafs;		//global tree上の子木の葉の数(たとえlocal tree上で親子関係があったとしても兄弟ノードの数は足されないことに注意)
		int treeEdges, nonTreeEdges;	//ビットセットで、ビットiはlocal treeとglobal tree上の子孫の頂点にレベルiの木(resp.非木)辺が1つ以上接しているかを表す
		int level;			//global tree上のレベル
		Node() :
			left(NULL), right(NULL), mid(NULL), parent(NULL),
			numLeafs(0), treeEdges(0), nonTreeEdges(0), level(-1) { }
	};
	std::vector<Node> vertexNodes;
	std::vector<bool> isTreeEdge;
	//その辺が存在しないことを-1で表す
	std::vector<int> edgeLevel;
	//無向辺: edge, 有向辺: arc と呼び分けることにする
	//arcの先の頂点
	std::vector<int> arcHead;		//Edge×2 → Vertex
	//頂点ごとにレベルごとにtree/non tree edgesが存在するかどうかのbitset
	std::vector<int> levelTreeEdges, levelNonTreeEdges;	//Vertex -> Bitset
	//頂点ごとのincident arcsの連結リスト
	std::vector<int> firstTreeArc, firstNonTreeArc;	//Vertex → Edge×2＋⊥
	//特定のレベルのリストをO(log n)で取得できるようにするために、連結リストを2段階にする
	//nextLevelArc,prevLevelArcはlevelごとの最初のエントリーにのみ保持される
	std::vector<int> nextLevelArc, nextPeerArc, prevLevelArc, prevPeerArc;	//Edge×2 → Edge×2＋⊥
	//使いまわして使う一時的なもの。サイズはそれぞれM, N
	std::vector<bool> edgeVisited, vertexVisited;
	//internal nodeたち
	std::vector<Node> internalNodes;
	std::vector<Node*> internalNodeFreeList;

	bool isLocalRoot(const Node *a) const {
		return !a->parent || a->parent->mid == a;
	}

	void updateNode(Node *a) const {
		int v = getVertexIndex(a);
		int treeEdges = 0, nonTreeEdges = 0;
		if (a->left) {
			treeEdges |= a->left->treeEdges;
			nonTreeEdges |= a->left->nonTreeEdges;
		}
		if (a->mid) {
			treeEdges |= a->mid->treeEdges;
			nonTreeEdges |= a->mid->nonTreeEdges;
		}
		if (a->right) {
			treeEdges |= a->right->treeEdges;
			nonTreeEdges |= a->right->nonTreeEdges;
		}
		if (v != -1) {
			treeEdges |= levelTreeEdges[v];
			nonTreeEdges |= levelNonTreeEdges[v];
		}
		a->treeEdges = treeEdges;
		a->nonTreeEdges = nonTreeEdges;
	}

	//rotateはupdateしない
	void rotateR(Node *a) const {
		Node *q = a->parent, *r = q->parent;
		if (q->left = a->right) a->right->parent = q;
		a->right = q; q->parent = a;
		if (a->parent = r) {
			if (r->left == q) r->left = a;
			else if (r->right == q) r->right = a;
			else if (r->mid == q) r->mid = a;
		}
	}
	void rotateL(Node *a) const {
		Node *q = a->parent, *r = q->parent;
		if (q->right = a->left) a->left->parent = q;
		a->left = q; q->parent = a;
		if (a->parent = r) {
			if (r->left == q) r->left = a;
			else if (r->right == q) r->right = a;
			else if (r->mid == q) r->mid = a;
		}
	}

	//localなsplay
	void localSplay(Node *a) {
		//この時点でaはupdateされている必要がある。
		//ループ中aはupdateせず、最後に1度だけupdateする
		if (isLocalRoot(a)) return;
		do {
			Node *q = a->parent;
			if (isLocalRoot(q)) {
				if (q->left == a) {
					rotateR(a);
					updateNode(a->right);
				}
				else {
					rotateL(a);
					updateNode(a->left);
				}
			}
			else {
				Node *r = q->parent;
				if (r->left == q) {
					if (q->left == a) {
						rotateR(q), rotateR(a);
						updateNode(q->right), updateNode(q);
					}
					else {
						rotateL(a), rotateR(a);
						updateNode(a->left), updateNode(a->right);
					}
				}
				else {
					if (q->right == a) {
						rotateL(q), rotateL(a);
						updateNode(q->left), updateNode(q);
					}
					else {
						rotateR(a), rotateL(a);
						updateNode(a->left), updateNode(a->right);
					}
				}
			}
		} while (!isLocalRoot(a));
		updateNode(a);
	}

	Node *newNode() {
		assert(!internalNodeFreeList.empty());
		Node *p = internalNodeFreeList.back(); internalNodeFreeList.pop_back();
		new(p) Node();

		return p;
	}
	void freeNode(Node *&a) {
		assert(getVertexIndex(a) == -1);

		a->left = a->right = a->parent = a->mid = reinterpret_cast<Node*>(0xdeaddead);
		internalNodeFreeList.push_back(a);
		a = NULL;
	}

	//global tree上での親ノードを取得する
	Node *globalParent(Node *a) {
		localSplay(a);
		return a->parent;
	}
	//globalParentと同じだがsplayせずに取得する
	Node *globalParentNoSplay(Node *a) {
		while (!isLocalRoot(a)) a = a->parent;
		return a->parent;
	}
	//global tree上での根ノードを取得する
	Node *getRootNode(int u) {
		Node *a = &vertexNodes[u];
		while (a->parent) a = globalParent(a);
		return a;
	}
	//aからrootへのパスを更新する
	void updatePath(Node *a) {
		while (a) {
			updateNode(a);
			localSplay(a);
			a = a->parent;
		}
	}

	//local tree上でaを削除する(切り離す)。aのglobal tree上の親を返す。cutNodeなどで内部的に用いるためのもの
	Node *deleteNode(Node *a) {
		localSplay(a);
		Node *r = a->left, *p = a->parent;
		if (!r) {
			if (r = a->right) r->parent = a->parent;
			if (a->parent) a->parent->mid = r;
		}
		else {
			while (r->right) r = r->right;
			localSplay(r);
			assert(r->right == a && !a->left);
			Node *b = a->right;
			if (r->right = b) b->parent = r;
			updateNode(r);
		}
		a->left = a->right = a->parent = NULL;
		updateNode(a);
		return p;
	}
	//global tree上でaから親への辺をカットする
	void cutNode(Node *a) {
		int numLeafs = a->numLeafs;
		Node *b = deleteNode(a);
		while (b) {
			updateNode(b);
			b->numLeafs -= numLeafs;
			b = globalParent(b);
		}
	}
	//aが子,bが親としてglobal tree上でリンクする
	void linkNode(Node *a, Node *b) {
		assert(!a->left && !a->right && !a->parent);
		int numLeafs = a->numLeafs;
		a->parent = b;
		if (a->left = b->mid) a->left->parent = a;
		b->mid = a;
		updateNode(a);
		while (b) {
			updateNode(b);
			b->numLeafs += numLeafs;
			b = globalParent(b);
		}
	}

	//local search treeをマージする
	//親がいないように切り離してからmergeする必要がある
	void mergeNode(Node *a, Node *b) {
		assert(!a->parent && !a->left && !a->right && !b->parent && !b->left && !b->right);
		Node *c = newNode();
		if (c->left = a->mid) c->left->parent = c;
		if (c->right = b->mid) c->right->parent = c;
		c->parent = a, a->mid = c;
		updateNode(c);
		updateNode(a);
		deleteNode(c);
		freeNode(c);
		b->mid = NULL;
		a->numLeafs += b->numLeafs;
		freeNode(b);
	}

	//レベルがちょうどlvになるように、ノードが省略されている場合は新たに作って返す
	Node *getLevelNode(Node *a, int lv) {
		if (a->level == lv) return a;
		Node *b = newNode();
		if (a->level > lv) {
			Node *p = a->parent;
			if (p) {
				if (p->left == a) p->left = b;
				else if (p->right == a) p->right = b;
				else p->mid = b;
			}
			b->parent = p;
			b->mid = a; a->parent = b;
			if (b->left = a->left) b->left->parent = b;
			if (b->right = a->right) b->right->parent = b;
			a->left = a->right = NULL;
			updateNode(a);
			updateNode(b);
			b->numLeafs = a->numLeafs;
			b->level = lv;
		}
		else {
			assert(false);
		}
		return b;
	}

	//aの子が1つだけだったら無駄なのでcontractする。下のノードを残すようにする
	Node *contractOneChildNode(Node *a) {
		Node *b = a->mid;
		if (!(b && !b->left && !b->right)) return a;
		Node *p = a->parent;
		b->parent = p;
		if (p) {
			if (p->left == a) p->left = b;
			else if (p->right == a) p->right = b;
			else p->mid = b;
		}
		if (b->left = a->left) b->left->parent = b;
		if (b->right = a->right) b->right->parent = b;
		updateNode(b);
		freeNode(a);
		return b;
	}

	//edgeからarcを取得する。arcは向きがあるので2つに対応する
	int arc1(int ei) const { return ei; }
	int arc2(int ei) const { return ei + numMaxEdges(); }
	//arcからedgeを取得する
	int arcEdge(int i) const { return i >= numMaxEdges() ? i - numMaxEdges() : i; }

	//vはarcのtail
	void insertArcToList(int i, int v) {
		int lv = edgeLevel[arcEdge(i)];
		bool treeEdge = isTreeEdge[arcEdge(i)];
		std::vector<int> &first = treeEdge ? firstTreeArc : firstNonTreeArc;

		int it = first[v], prev = -1;
		while (it != -1 && edgeLevel[arcEdge(it)] < lv) {
			prev = it;
			it = nextLevelArc[it];
		}

		prevPeerArc[i] = -1;
		if ((prevLevelArc[i] = prev) != -1) nextLevelArc[prev] = i;
		else first[v] = i;

		int nextPeer = -1, nextLevel = -1;
		if (it != -1 && edgeLevel[arcEdge(it)] == lv) {
			nextPeer = it;
			nextLevel = nextLevelArc[it];
			nextLevelArc[it] = prevLevelArc[it] = -1;
		}
		else {
			nextLevel = it;
			std::vector<int> &levelEdges = treeEdge ? levelTreeEdges : levelNonTreeEdges;
			levelEdges[v] |= 1 << lv;
		}
		if ((nextPeerArc[i] = nextPeer) != -1) prevPeerArc[nextPeer] = i;
		if ((nextLevelArc[i] = nextLevel) != -1) prevLevelArc[nextLevel] = i;
	}
	void removeArcFromList(int i, int v) {
		int lv = edgeLevel[arcEdge(i)];
		bool treeEdge = isTreeEdge[arcEdge(i)];
		std::vector<int> &first = treeEdge ? firstTreeArc : firstNonTreeArc;

		int nextPeer = nextPeerArc[i], prevPeer = prevPeerArc[i];
		if (prevPeer != -1) nextPeerArc[prevPeer] = nextPeer;
		if (nextPeer != -1) prevPeerArc[nextPeer] = prevPeer;
		nextPeerArc[i] = prevPeerArc[i] = -2;

		if (prevPeer == -1) {
			int nextLevel = nextLevelArc[i], prevLevel = prevLevelArc[i];
			if (nextPeer != -1) {
				nextLevelArc[nextPeer] = nextLevel;
				prevLevelArc[nextPeer] = prevLevel;
				if (prevLevel != -1) nextLevelArc[prevLevel] = nextPeer;
				else first[v] = nextPeer;
				if (nextLevel != -1) prevLevelArc[nextLevel] = nextPeer;
			}
			else {
				if (prevLevel != -1) nextLevelArc[prevLevel] = nextLevel;
				else first[v] = nextLevel;
				if (nextLevel != -1) prevLevelArc[nextLevel] = prevLevel;

				std::vector<int> &levelEdges = treeEdge ? levelTreeEdges : levelNonTreeEdges;
				levelEdges[v] &= ~(1 << lv);
			}
		}
		else assert(nextLevelArc[i] == -1 && prevLevelArc[i] == -1);
		nextLevelArc[i] = prevLevelArc[i] = -2;
	}

	void insertEdgeToListNoUpdate(int ei) {
		insertArcToList(arc1(ei), arcHead[arc2(ei)]);
		insertArcToList(arc2(ei), arcHead[arc1(ei)]);
	}
	void removeEdgeFromListNoUpdate(int ei) {
		removeArcFromList(arc1(ei), arcHead[arc2(ei)]);
		removeArcFromList(arc2(ei), arcHead[arc1(ei)]);
	}
	void updateEdgeStatus(int ei) {
		updatePath(&vertexNodes[arcHead[arc1(ei)]]);
		updatePath(&vertexNodes[arcHead[arc2(ei)]]);
	}

	//このノードがvertex nodeである場合頂点番号を返す。そうでない場合-1を返す
	int getVertexIndex(const Node *a) const {
		const Node *first = &vertexNodes[0];
		if (first <= a && a < first + numVertices())
			return a - first;
		else
			return -1;
	}

	template<bool TreeEdge>
	inline int getFirstLevelArc(int v, int lv) {
		int it = TreeEdge ? firstTreeArc[v] : firstNonTreeArc[v];
		while (it != -1 && edgeLevel[arcEdge(it)] < lv)
			it = nextLevelArc[it];
		if (it == -1 || edgeLevel[arcEdge(it)] != lv) return -1;
		return it;
	}
	//根だけは左右(left,right)には行けない
	template<bool TreeEdge>
	inline void enumArcAddRoot(Node *a, int lv, std::vector<Node*> &stk, std::vector<int> &arcs) {
		int Node::*edgeBitset = TreeEdge ? &Node::treeEdges : &Node::nonTreeEdges;
		if (a->mid && (a->mid->*edgeBitset >> lv & 1))
			stk.push_back(a->mid);
		int v = getVertexIndex(a);
		if (v != -1) {
			int it = getFirstLevelArc<TreeEdge>(v, lv);
			if (it != -1) arcs.push_back(it);
		}
	}
	//enumArcNextがまだできるかどうか
	inline bool enumArcContinue(const std::vector<Node*> &stk, std::vector<int> &arcs) {
		return !stk.empty() || !arcs.empty();
	}
	//tree/nontree arcsを1つずつ列挙する
	template<bool TreeEdge>
	inline int enumArcNext(int lv, std::vector<Node*> &stk, std::vector<int> &arcs) {
		if (!arcs.empty()) {
			int currentArc = arcs.back();
			int next = nextPeerArc[currentArc];
			if (next == -1) arcs.pop_back();
			else arcs.back() = next;
			return currentArc;
		}
		int Node::*edgeBitset = TreeEdge ? &Node::treeEdges : &Node::nonTreeEdges;
		const std::vector<int> &levelEdges = TreeEdge ? levelTreeEdges : levelNonTreeEdges;
		int u;
		do {
			Node *a = stk.back(); stk.pop_back();
			assert(a->*edgeBitset >> lv & 1);
			if (a->left && (a->left->*edgeBitset >> lv & 1))
				stk.push_back(a->left);
			if (a->mid && (a->mid->*edgeBitset >> lv & 1))
				stk.push_back(a->mid);
			if (a->right && (a->right->*edgeBitset >> lv & 1))
				stk.push_back(a->right);
			u = getVertexIndex(a);
		} while (u == -1 || !(levelEdges[u] >> lv & 1));
		//この頂点から出てるレベルlvの木辺を列挙
		//木辺の次数がとても大きい頂点があるとone stepがboundしなくなってしまうので、遅延評価的にstateで保存しておく
		int it = getFirstLevelArc<TreeEdge>(u, lv);
		assert(it != -1);
		assert(edgeLevel[arcEdge(it)] == lv);
		arcs.push_back(it);
		return enumArcNext<TreeEdge>(lv, stk, arcs);
	}


	//global node aの木上で(v,w)を切った時に残る2つの木のうちサイズが小さいものを見つけ、
	//その側ua∈{va,wa}とそれに属するglobal tree中のaの子たちを返す
	Node *findSmallerTree(Node *a, Node *va, Node *wa, std::vector<Node*> &uNodes, std::vector<int> &uEdges, int &uSize) {
		int lv = a->level;
		int vsize = va->numLeafs, wsize = wa->numLeafs;
		std::vector<Node*> stkv, stkw, vNodes, wNodes;
		std::vector<int> vArcs, wArcs, vEdges, wEdges, xEdges;

		enumArcAddRoot<true>(va, lv, stkv, vArcs);
		enumArcAddRoot<true>(wa, lv, stkw, wArcs);
		while (enumArcContinue(stkv, vArcs) && enumArcContinue(stkw, wArcs)) {
			if (vsize <= wsize)
				vsize += findSmallerTreeStep(lv, stkv, vArcs, vNodes, vEdges);
			else
				wsize += findSmallerTreeStep(lv, stkw, wArcs, wNodes, wEdges);
		}
		for (int i = 0; i < (int)vEdges.size(); i++)
			edgeVisited[vEdges[i]] = false;
		for (int i = 0; i < (int)wEdges.size(); i++)
			edgeVisited[wEdges[i]] = false;

		Node *ua;
		if (!enumArcContinue(stkv, vArcs)) {
			ua = va, uSize = vsize, uNodes.swap(vNodes);
			uEdges.swap(vEdges), xEdges.swap(wEdges);
		}
		else {
			ua = wa, uSize = wsize, uNodes.swap(wNodes);
			uEdges.swap(wEdges), xEdges.swap(vEdges);
		}
		return ua;
	}

	inline int findSmallerTreeStep(int lv, std::vector<Node*> &stk, std::vector<int> &arcs, std::vector<Node*> &nodes, std::vector<int> &edges) {
		int i = enumArcNext<true>(lv, stk, arcs);
		int ei = arcEdge(i);
		if (edgeVisited[ei]) return 0;
		edgeVisited[ei] = true;
		edges.push_back(ei);
		Node *b = &vertexNodes[arcHead[i]];
		while (true) {
			Node *p = globalParent(b);	//探索してるとこをsplayすることはないはず
			if (p->level <= lv) break;
			b = p;
		}
		assert(lv < b->level);
		enumArcAddRoot<true>(b, lv, stk, arcs);	//向こう側も探索
		nodes.push_back(b);
		return b->numLeafs;
	}

	//aのsubtreeにincidentしてるレベルlvのnontree edgeを1つサンプルする
	//ランダムにサンプルってできないかと思うのだけど…とりあえずランダムさは無くやる。構造自体をランダムにするとか？
	int sampleNonTreeEdge(Node *a, int lv) {
		int v = getVertexIndex(a);
		if (v == -1) {
			Node *b = a->mid;
			if (!(b->nonTreeEdges >> lv & 1)) return -1;
			while (true) {
				v = getVertexIndex(b);
				if (v != -1 && (levelNonTreeEdges[v] >> lv & 1))
					break;
				if (b->left && (b->left->nonTreeEdges >> lv & 1))
					b = b->left;
				else if (b->right && (b->right->nonTreeEdges >> lv & 1))
					b = b->right;
				else if (b->mid && (b->mid->nonTreeEdges >> lv & 1))
					b = b->mid;
				else assert(false);
			}
		}
		return getFirstLevelArc<false>(v, lv);
	}

	//aのレベルでvとwを連結させる辺を見つける。見つかったかどうかを返す
	//va,waはv,wの祖先でglobal tree上でのaの子ノード
	bool replaceRec(int lv, Node *a, Node *va, Node *wa) {
		//小さい方の木T_uを見つける
		std::vector<Node*> uNodes; std::vector<int> uEdges; int uSize;
		Node *ua_t = findSmallerTree(a, va, wa, uNodes, uEdges, uSize);
		Node *ua = getLevelNode(ua_t, lv + 1);

		//T_uをglobal treeの構造的にレベルアップさせる
		cutNode(ua);
		for (int i = 0; i < (int)uNodes.size(); i++) {
			Node *n = getLevelNode(uNodes[i], lv + 1);
			cutNode(n);
			mergeNode(ua, n);
		}
		//uaはcutしたままにしておく

		int replacementEdge = -1;
		std::vector<int> levelupEdges;
		//T_uのこのレベルのtree edgesをレベルアップさせるためにlevelupEdgesに入れとく
		levelupEdges.swap(uEdges);

		//まず何個かサンプリングする
		for (int k = 1; k <= uSize; k <<= 1) {
			int i = sampleNonTreeEdge(ua, lv);
			if (i == -1) break;
			int ei = arcEdge(i);
			//lvまで登る
			Node *b = &vertexNodes[arcHead[i]];
			while (b->parent && b->level > lv + 1) {
				b = globalParent(b);
			}
			if (b == ua) {
				//両端がT_u側にある辺である
				//サンプリングのために今ここでレベルアップする
				removeEdgeFromListNoUpdate(ei);
				edgeLevel[ei] ++;
				insertEdgeToListNoUpdate(ei);
				updateEdgeStatus(ei);
			}
			else {
				//replacement edgeが見つかった
				replacementEdge = ei;
				break;
			}
		}

		int treeEdgeCount = levelupEdges.size();
		//Test-All的な
		if (replacementEdge == -1) {
			//replacement edgeは少ないと仮定してやる

			std::vector<Node*> stk; static std::vector<int> arcs;
			stk.clear(); arcs.clear();
			//このレベルのT_uのnon tree edgesを列挙する
			enumArcAddRoot<false>(ua, lv, stk, arcs);
			while (enumArcContinue(stk, arcs)) {
				int i = enumArcNext<false>(lv, stk, arcs);
				int ei = arcEdge(i);
				vertexVisited[arcHead[i == arc1(ei) ? arc2(ei) : arc1(ei)]] = true;
				if (edgeVisited[ei]) continue;
				edgeVisited[ei] = true;

				levelupEdges.push_back(ei);
			}

			for (int i = treeEdgeCount; i < (int)levelupEdges.size(); i++) {
				int ei = levelupEdges[i];
				if (!vertexVisited[arcHead[arc1(ei)]] || !vertexVisited[arcHead[arc2(ei)]]) {
					replacementEdge = ei;
					break;
				}
			}
		}
		for (int i = 0; i < (int)levelupEdges.size(); i++) {
			int ei = levelupEdges[i];
			if (treeEdgeCount <= i) {
				//replacement edgeじゃないならTest-Allで両方の向きが見つかってるはず
				if (!vertexVisited[arcHead[arc1(ei)]] || !vertexVisited[arcHead[arc2(ei)]]) {
					//replacement edgeはレベルアップしない(できない)
					//replacement edgeばかりの時にlevel upできなくてpayできないので最初にサンプリングしてる
					if (replacementEdge == -1) {
						replacementEdge = ei;
					}
					continue;
				}
			}
			//見たedgeを実際にレベルアップさせる
			removeEdgeFromListNoUpdate(ei);
			edgeLevel[ei] ++;
			insertEdgeToListNoUpdate(ei);
			updateEdgeStatus(ei);
		}
		for (int i = treeEdgeCount; i < (int)levelupEdges.size(); i++) {
			int ei = levelupEdges[i];
			edgeVisited[ei] = false;
			vertexVisited[arcHead[arc1(ei)]] = false;
			vertexVisited[arcHead[arc2(ei)]] = false;
		}
		if (replacementEdge != -1) {
			//replacement edgeが見つかった場合
			removeEdgeFromListNoUpdate(replacementEdge);
			isTreeEdge[replacementEdge] = true;
			insertEdgeToListNoUpdate(replacementEdge);
			updateEdgeStatus(replacementEdge);
			linkNode(ua, a);	//uaを連結させる
			a = contractOneChildNode(a);
			ua = contractOneChildNode(ua);
			edgeVisited[replacementEdge] = false;
			return true;
		}
		//replacement edgeが見つからなかった場合
		Node *up = newNode();
		up->level = lv;
		linkNode(ua, up);
		a = contractOneChildNode(a);
		up = contractOneChildNode(up);
		if (up == ua) up = ua = contractOneChildNode(ua);
		else ua = contractOneChildNode(ua);
		if (lv > 0) {
			Node *ap = globalParent(a);
			Node *p = ap && ap->level == lv - 1 ? ap : getLevelNode(a, lv - 1);
			linkNode(up, p);
			return replaceRec(lv - 1, p, up, a);
		}
		else {
			return false;
		}
	}

	//aとbを連結させる辺を見つける。見つかったかどうかを返す
	bool replace(Node *a, Node *b) {
		//v,wのglobal tree上のlcaを見つける。ap,bpにそのすぐ下の子を保持しておく
		Node *ap = NULL, *bp = NULL;
		assert(a != b);
		while (a != b) {
			assert(a && b);
			if (a->level >= b->level)
				ap = a, a = globalParent(a);
			else if (a->level < b->level)
				bp = b, b = globalParent(b);
		}
		return replaceRec(a->level, a, ap, bp);
	}

	//コピコンはとりあえずdelete
	FullyDynamicConnectivity(const FullyDynamicConnectivity &that) { assert(false); }
	FullyDynamicConnectivity &operator=(const FullyDynamicConnectivity &that) { assert(false); }

public:
	FullyDynamicConnectivity() { }
	~FullyDynamicConnectivity() { }

	//floor(log_2(N))
	static int calcMaxLevel(int N) {
		int maxLevel = 0;
		while (1 << maxLevel <= N / 2) maxLevel++;
		return maxLevel;
	}

	//頂点数N, 最大辺数Mとして初期化する(edgeless graphとなる)
	void init(int N, int M) {
		internalNodeFreeList.clear();
		//子を2つ以上まとめるノードになるには辺が必要。その他に一時的なノード分として＋α
		//よく考えてないのでだめかも。とにかくランダムケースではinternal nodeはとても少ない(だからテストが難しい)
		internalNodes.resize(M + 5);
		internalNodeFreeList.resize(internalNodes.size());
		for (int i = 0; i < (int)internalNodes.size(); i++)
			internalNodeFreeList[i] = &internalNodes[i];

		int maxLevel = calcMaxLevel(N);

		vertexNodes.assign(N, Node());
		for (int i = 0; i < N; i++) {
			vertexNodes[i].level = maxLevel;
			vertexNodes[i].numLeafs = 1;
		}

		isTreeEdge.assign(M, false);
		edgeLevel.assign(M, -1);

		arcHead.assign(M * 2, -1);

		levelTreeEdges.assign(N, 0);
		levelNonTreeEdges.assign(N, 0);

		firstTreeArc.assign(N, -1);
		firstNonTreeArc.assign(N, -1);

		nextLevelArc.assign(M * 2, -2);
		nextPeerArc.assign(M * 2, -2);
		prevLevelArc.assign(M * 2, -2);
		prevPeerArc.assign(M * 2, -2);

		edgeVisited.assign(M, false);
		vertexVisited.assign(N, false);
	}
	int numVertices() const { return vertexNodes.size(); }
	int numMaxEdges() const { return isTreeEdge.size(); }
	//uとvが連結しているかどうかを返す
	bool isConnected(int v, int w) {
		assert(0 <= v && v < numVertices() && 0 <= w && w < numVertices());
		return getRootNode(v) == getRootNode(w);
	}
	//vが属する連結成分のサイズを返す
	int getConnectedComponentSize(int v) {
		assert(0 <= v && v < numVertices());
		return getRootNode(v)->numLeafs;
	}
	//辺(u,v)を追加する。eiは辺のインデックスで、削除する時に指定する
	//connected componentsの数が減ったか(新たに連結されたか)を返す
	bool insertEdge(int ei, int v, int w) {
		assert(0 <= ei && ei < numMaxEdges() && 0 <= v && v < numVertices() && 0 <= w && w < numVertices());
		assert(edgeLevel[ei] == -1);

		Node *vRoot = getRootNode(v);
		Node *wRoot = getRootNode(w);
		bool treeEdge = vRoot != wRoot;

		isTreeEdge[ei] = treeEdge;
		edgeLevel[ei] = 0;

		int a1 = arc1(ei), a2 = arc2(ei);
		assert(arcHead[a1] == -1 && arcHead[a2] == -1);
		arcHead[a1] = w, arcHead[a2] = v;

		if (v != w) {	//ループは見たくないのでリストには登録しない
			insertEdgeToListNoUpdate(ei);
			updateEdgeStatus(ei);
		}

		if (treeEdge) {
			Node *v0 = getLevelNode(vRoot, 0), *w0 = getLevelNode(wRoot, 0);
			mergeNode(v0, w0);
		}
		return treeEdge;
	}
	//辺を削除する。eiは辺のインデックス
	//connected componentsの数が増えたか(新たに分離したか)を返す
	bool deleteEdge(int ei) {
		assert(0 <= ei && ei < numMaxEdges());
		assert(edgeLevel[ei] != -1);

		int a1 = arc1(ei), a2 = arc2(ei);
		int v = arcHead[a2], w = arcHead[a1];

		if (v != w) {	//ループは登録されていない
			removeEdgeFromListNoUpdate(ei);
			updateEdgeStatus(ei);
		}

		arcHead[a1] = arcHead[a2] = -1;

		bool treeEdge = isTreeEdge[ei];
		isTreeEdge[ei] = false;
		edgeLevel[ei] = -1;

		bool splited;
		if (!treeEdge) splited = false;
		else splited = !replace(&vertexNodes[v], &vertexNodes[w]);
		return splited;
	}
};

void solve_abc120_d() {
	int N = readint(), M = readint();
	static FullyDynamicConnectivity fdc;
	fdc.init(N, M);
	vector<int>a(M), b(M);
	FOR(i, 0, M) {
		a[i] = readint() - 1, b[i] = readint() - 1;
		fdc.insertEdge(i, a[i], b[i]);
	}
	LL ans = 0;
	FOR(i, 0, M) {
		bool fall = fdc.deleteEdge(i);
		if (fall) {
			ans += fdc.getConnectedComponentSize(a[i])*(LL)fdc.getConnectedComponentSize(b[i]);
		}
		printLL(ans);
	}

}
int main() {
	solve_abc120_d();
	return 0;
}

Measured memory_bytes: 18992