#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL_TEST
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // LOCAL_TEST
using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using vs = vector<string>; using vvs = vector<vector<string>>; using vvvs = vector<vector<vector<string>>>;
template<typename T> vector<vector<T>> vv(int h, int w, T val = T()) { return vector(h, vector<T>(w, val)); }
template<typename T> vector<vector<vector<T>>> vvv(int h1, int h2, int h3, T val = T()) { return vector(h1, vector(h2, vector<T>(h3, val))); }
template<typename T> vector<vector<vector<vector<T>>>> vvvv(int h1, int h2, int h3, int h4, T val = T()) { return vector(h1, vector(h2, vector(h3, vector<T>(h4, val)))); }
template <class T> using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.14159265358979323;
constexpr int INF = 100100111; constexpr ll INFL = 3300300300300300491LL;
float EPS = 1e-8; double EPSL = 1e-10;
struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } nyan;
#define all(a) (a).begin(), (a).end()
#define len(x) ((ll)(x).size())
#define sz(x) ((ll)(x).size())
#define rep1(n) for(ll dummy_iter = 0LL; dummy_iter < n; ++dummy_iter) // 0,1,...,n-1
#define rep2(i, n) for(ll i = 0LL, i##_counter = 0LL; i##_counter < ll(n); ++(i##_counter), (i) = i##_counter) // i=0,1,...,n-1
#define rep3(i, s, t) for(ll i = ll(s), i##_counter = ll(s); i##_counter < ll(t); ++(i##_counter), (i) = (i##_counter)) // i=s,s+1,...,t-1
#define rep4(i, s, t, step) for(ll i##_counter = step > 0 ? ll(s) : -ll(s), i##_end = step > 0 ? ll(t) : -ll(t), i##_step = abs(step), i = ll(s); i##_counter < i##_end; i##_counter += i##_step, i = step > 0 ? i##_counter : -i##_counter) // i=s,s+step,...,<t
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define repe(a, v) for(auto& a : (v)) // iterate over all elements in v
#define smod(n, m) ((((n) % (m)) + (m)) % (m))
#define sdiv(n, m) (((n) - smod(n, m)) / (m))
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());}
int Yes(bool b=true) { cout << (b ? "Yes\n" : "No\n"); return 0; };
int YES(bool b=true) { cout << (b ? "YES\n" : "NO\n"); return 0; };
int No(bool b=true) {return Yes(!b);};
int NO(bool b=true) {return YES(!b);};
template<typename T, size_t N> T max(array<T, N>& a) { return *max_element(all(a)); };
template<typename T, size_t N> T min(array<T, N>& a) { return *min_element(all(a)); };
template<typename T> T max(vector<T>& a) { return *max_element(all(a)); };
template<typename T> T min(vector<T>& a) { return *min_element(all(a)); };
template<typename T> vector<T> vec_slice(const vector<T>& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> T sum(vector<T>& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };
template <class T> inline vector<T>& operator--(vector<T>& v) { repe(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repe(x, v) ++x; return v; }
ll powm(ll a, ll n, ll mod=INFL) {
ll res = 1;
while (n > 0) {
if (n & 1) res = (res * a) % mod;
if (n > 1) a = (a * a) % mod;
n >>= 1;
}
return res;
}
ll sqrtll(ll x) {
assert(x >= 0);
ll rev = sqrt(x);
while(rev * rev > x) --rev;
while((rev+1) * (rev+1)<=x) ++rev;
return rev;
}
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; }
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p);
template <class T> inline istream& operator>>(istream& is, vector<T>& v);
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repe(x, v) is >> x; return is; }
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << " " << p.second; return os; }
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { os << v.at(i); if (i != sz(v) - 1) os << " "; } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st) { ll cnt = 0; for (auto &e : st) { os << e << (++cnt != (int)st.size() ? " " : ""); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front(); q.pop_front(); if (q.size()) os << " "; } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; }
#define dout(x) cout << fixed << setprecision(10) << x << endl
#define read1(a) cin >> a;
#define read2(a, b) cin >> a >> b;
#define read3(a, b, c) cin >> a >> b >> c;
#define read4(a, b, c, d) cin >> a >> b >> c >> d;
#define read5(a, b, c, d, e) cin >> a >> b >> c >> d >> e;
#define read6(a, b, c, d, e, f) cin >> a >> b >> c >> d >> e >> f;
#define read7(a, b, c, d, e, f, g) cin >> a >> b >> c >> d >> e >> f >> g;
#define read8(a, b, c, d, e, f, g, h) cin >> a >> b >> c >> d >> e >> f >> g >> h;
#define overload_read(a, b, c, d, e, f, g, h, i, ...) i
#define read(...) overload_read(__VA_ARGS__,read8,read7,read6,read5,read4,read3,read2,read1)(__VA_ARGS__)
#define inner_output1(a) cout << a << endl;
#define inner_output2(a, b) cout << a << " " << b << endl;
#define inner_output3(a, b, c) cout << a << " " << b << " " << c << endl;
#define inner_output4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl;
#define inner_output5(a, b, c, d, e) cout << a << " " << b << " " << c << " " << d << " " << e << endl;
#define inner_output6(a, b, c, d, e, f) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
#define inner_output7(a, b, c, d, e, f, g) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;
#define inner_output8(a, b, c, d, e, f, g, h) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << endl;
#define overload_inner_output(a, b, c, d, e, f, g, h, i, ...) i
#define out(...) overload_inner_output(__VA_ARGS__,inner_output8,inner_output7,inner_output6,inner_output5,inner_output4,inner_output3,inner_output2,inner_output1)(__VA_ARGS__)
#define ii(...) ll __VA_ARGS__; read(__VA_ARGS__)
#define si(...) string __VA_ARGS__; read(__VA_ARGS__)
#define ci(...) char __VA_ARGS__; read(__VA_ARGS__)
#define di(...) double __VA_ARGS__; read(__VA_ARGS__)
#define li(name,size); vector<ll> name(size); read(name)
#define lli(name,H,W); vector name(H,vector<ll>(W));rep(i,H) cin >> name[i];
#ifdef LOCAL_TEST
#define inner_debug1(a) cerr << "[DEBUG#" << __LINE__ << "] " << #a << " = " << a << endl;
#define inner_debug2(a, b) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << endl;
#define inner_debug3(a, b, c) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << endl;
#define inner_debug4(a, b, c, d) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << endl;
#define inner_debug5(a, b, c, d, e) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << endl;
#define inner_debug6(a, b, c, d, e, f) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << endl;
#define inner_debug7(a, b, c, d, e, f, g) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << ", " << #g << " = " << g << endl;
#define inner_debug8(a, b, c, d, e, f, g, h) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << ", " << #g << " = " << g << ", " << #h << " = " << h << endl;
#define overload_inner_debug(a, b, c, d, e, f, g, h, i, ...) i
#define debug(...) overload_inner_debug(__VA_ARGS__,inner_debug8,inner_debug7,inner_debug6,inner_debug5,inner_debug4,inner_debug3,inner_debug2,inner_debug1)(__VA_ARGS__)
#else
#define debug(...);
#endif // LOCAL_TEST
inline ll ctz(ll x) { return __builtin_ctzll(x);}
inline ll clz(ll x) { return __builtin_clzll(x);}
inline ll popcount(ll x) { return __builtin_popcountll(x);}
inline bool inrange(ll x, ll a, ll b) { return a <= x && x < b; }
template <typename T> inline ll findll(vector<T>& v, T x) { auto tmp = find(all(v), x);if(tmp == v.end()){return -1;}else{return distance(v.begin(),tmp); }}
inline ll findll(string& s, char x) { auto tmp = find(all(s), x);if(tmp == s.end()){return -1;}else{return distance(s.begin(),tmp); }}
#include <vector>
#include <utility>
#include <cassert>
#include <cplib/nachia/csr-array.hpp>
namespace nachia{
struct Graph {
public:
struct Edge{
int from, to;
void reverse(){ std::swap(from, to); }
int xorval() const { return from ^ to; }
};
Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {}
Graph(int n, const std::vector<std::pair<int, int>>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){
m_e.resize(edges.size());
for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second };
}
template<class Cin>
static Graph Input(Cin& cin, int n, bool undirected, int m, int offset = 0){
Graph res(n, undirected, m);
for(int i=0; i<m; i++){
int u, v; cin >> u >> v;
res[i].from = u - offset;
res[i].to = v - offset;
}
return res;
}
int numVertices() const noexcept { return m_n; }
int numEdges() const noexcept { return int(m_e.size()); }
int addNode() noexcept { return m_n++; }
int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; }
Edge& operator[](int ei) noexcept { return m_e[ei]; }
const Edge& operator[](int ei) const noexcept { return m_e[ei]; }
Edge& at(int ei) { return m_e.at(ei); }
const Edge& at(int ei) const { return m_e.at(ei); }
auto begin(){ return m_e.begin(); }
auto end(){ return m_e.end(); }
auto begin() const { return m_e.begin(); }
auto end() const { return m_e.end(); }
bool isUndirected() const noexcept { return m_isUndir; }
void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); }
void contract(int newV, const std::vector<int>& mapping){
assert(numVertices() == int(mapping.size()));
for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; }
m_n = newV;
}
std::vector<Graph> induce(int num, const std::vector<int>& mapping) const {
int n = numVertices();
assert(n == int(mapping.size()));
for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
std::vector<int> indexV(n), newV(num);
for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
std::vector<Graph> res; res.reserve(num);
for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected());
for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
return res;
}
CsrArray<int> getEdgeIndexArray(bool undirected) const {
std::vector<std::pair<int, int>> src;
src.reserve(numEdges() * (undirected ? 2 : 1));
for(int i=0; i<numEdges(); i++){
auto e = operator[](i);
src.emplace_back(e.from, i);
if(undirected) src.emplace_back(e.to, i);
}
return CsrArray<int>::Construct(numVertices(), src);
}
CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); }
CsrArray<int> getAdjacencyArray(bool undirected) const {
std::vector<std::pair<int, int>> src;
src.reserve(numEdges() * (undirected ? 2 : 1));
for(auto e : m_e){
src.emplace_back(e.from, e.to);
if(undirected) src.emplace_back(e.to, e.from);
}
return CsrArray<int>::Construct(numVertices(), src);
}
CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); }
private:
int m_n;
std::vector<Edge> m_e;
bool m_isUndir;
};
} // namespace nachia
#include <cplib/nachia/csr-array.hpp>
#include <vector>
#include <algorithm>
namespace nachia{
struct HeavyLightDecomposition{
private:
int N;
std::vector<int> P;
std::vector<int> PP;
std::vector<int> PD;
std::vector<int> D;
std::vector<int> I;
std::vector<int> rangeL;
std::vector<int> rangeR;
public:
HeavyLightDecomposition(const CsrArray<int>& E = CsrArray<int>::Construct(1, {}), int root = 0){
N = E.size();
P.assign(N, -1);
I = {root};
I.reserve(N);
for(int i=0; i<(int)I.size(); i++){
int p = I[i];
for(int e : E[p]) if(P[p] != e){
I.push_back(e);
P[e] = p;
}
}
std::vector<int> Z(N, 1);
std::vector<int> nx(N, -1);
PP.resize(N);
for(int i=0; i<N; i++) PP[i] = i;
for(int i=N-1; i>=1; i--){
int p = I[i];
Z[P[p]] += Z[p];
if(nx[P[p]] == -1) nx[P[p]] = p;
if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
}
for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;
PD.assign(N,N);
PD[root] = 0;
D.assign(N,0);
for(int p : I) if(p != root){
PP[p] = PP[PP[p]];
PD[p] = std::min(PD[PP[p]], PD[P[p]]+1);
D[p] = D[P[p]]+1;
}
rangeL.assign(N,0);
rangeR.assign(N,0);
for(int p : I){
rangeR[p] = rangeL[p] + Z[p];
int ir = rangeR[p];
for(int e : E[p]) if(P[p] != e) if(e != nx[p]){
rangeL[e] = (ir -= Z[e]);
}
if(nx[p] != -1){
rangeL[nx[p]] = rangeL[p] + 1;
}
}
I.resize(N);
for(int i=0; i<N; i++) I[rangeL[i]] = i;
}
HeavyLightDecomposition(const Graph& tree, int root = 0)
: HeavyLightDecomposition(tree.getAdjacencyArray(true), root) {}
int numVertices() const { return N; }
int depth(int p) const { return D[p]; }
int toSeq(int vtx) const { return rangeL[vtx]; }
int toVtx(int seqidx) const { return I[seqidx]; }
int toSeq2In(int vtx) const { return rangeL[vtx] * 2 - D[vtx]; }
int toSeq2Out(int vtx) const { return rangeR[vtx] * 2 - D[vtx] - 1; }
int parentOf(int v) const { return P[v]; }
int heavyRootOf(int v) const { return PP[v]; }
int heavyChildOf(int v) const {
if(toSeq(v) == N-1) return -1;
int cand = toVtx(toSeq(v) + 1);
if(PP[v] == PP[cand]) return cand;
return -1;
}
int lca(int u, int v) const {
if(PD[u] < PD[v]) std::swap(u, v);
while(PD[u] > PD[v]) u = P[PP[u]];
while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
return (D[u] > D[v]) ? v : u;
}
int dist(int u, int v) const {
return depth(u) + depth(v) - depth(lca(u,v)) * 2;
}
struct Range{
int l; int r;
int size() const { return r-l; }
bool includes(int x) const { return l <= x && x < r; }
};
std::vector<Range> path(int r, int c, bool include_root = true, bool reverse_path = false) const {
if(PD[c] < PD[r]) return {};
std::vector<Range> res(PD[c]-PD[r]+1);
for(int i=0; i<(int)res.size()-1; i++){
res[i] = { rangeL[PP[c]], rangeL[c]+1 };
c = P[PP[c]];
}
if(PP[r] != PP[c] || D[r] > D[c]) return {};
res.back() = { rangeL[r]+(include_root?0:1), rangeL[c]+1 };
if(res.back().l == res.back().r) res.pop_back();
if(!reverse_path) std::reverse(res.begin(),res.end());
else for(auto& a : res) a = { N - a.r, N - a.l };
return res;
}
Range subtree(int p) const { return { rangeL[p], rangeR[p] }; }
int median(int x, int y, int z) const {
return lca(x,y) ^ lca(y,z) ^ lca(x,z);
}
int la(int from, int to, int d) const {
if(d < 0) return -1;
int g = lca(from,to);
int dist0 = D[from] - D[g] * 2 + D[to];
if(dist0 < d) return -1;
int p = from;
if(D[from] - D[g] < d){ p = to; d = dist0 - d; }
while(D[p] - D[PP[p]] < d){
d -= D[p] - D[PP[p]] + 1;
p = P[PP[p]];
}
return I[rangeL[p] - d];
}
struct ChildrenIterRange {
struct Iter {
const HeavyLightDecomposition& hld; int s;
int operator*() const { return hld.toVtx(s); }
Iter& operator++(){
s += hld.subtree(hld.I[s]).size();
return *this;
}
Iter operator++(int) const { auto a = *this; return ++a; }
bool operator==(Iter& r) const { return s == r.s; }
bool operator!=(Iter& r) const { return s != r.s; }
};
const HeavyLightDecomposition& hld; int v;
Iter begin() const { return { hld, hld.rangeL[v] + 1 }; }
Iter end() const { return { hld, hld.rangeR[v] }; }
};
ChildrenIterRange children(int v) const {
return ChildrenIterRange{ *this, v };
}
};
} // namespace nachia
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
std::vector<int> parent_or_size;
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
#else
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
#endif
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
using namespace atcoder;
using namespace nachia;
ll op(ll a,ll b){
return a+b;
}
ll e(){
return 0;
}
ll mapping(ll f,ll x){
if(f !=INFL ) return f;
return x;
}
ll composition(ll f,ll g){
if(f != INFL) return f;
return g;
}
ll id(){
return INFL;
}
int main(){
ii(Q);
dsu uf(200000);
vector<pll> edges;
vector<ll> first(200000,-1);
vector<ll> time(200000,INFL);
vector<pll> querys;
ll cnt = 200000;
rep(i,Q){
ii(a,b);
a--;b--;
b+=100000;
querys.emplace_back(a,b);
if(uf.same(a,b)){
if(first[uf.leader(a)] == -1){
first[uf.leader(a)] = a;
time[uf.leader(a)] = i;
}
}else{
ll t;
ll f;
if((first[uf.leader(a)] != -1)&&(first[uf.leader(b)] != -1)){
a = first[uf.leader(a)];
b = first[uf.leader(b)];
}
if(time[uf.leader(a)] < time[uf.leader(b)]){
t = time[uf.leader(a)];
f = first[uf.leader(a)];
}else{
t = time[uf.leader(b)];
f = first[uf.leader(b)];
}
uf.merge(a,b);
cnt--;
edges.emplace_back(a,b);
first[uf.leader(a)] = f;
time[uf.leader(a)] = t;
}
}
Graph g(200001,true,0);
vector<bool> alr(200000,false);
ll debug_cnt = 0;
rep(i,len(edges)){
g.addEdge(edges[i].first,edges[i].second);
debug_cnt++;
}
rep(i,200000){
if(alr[uf.leader(i)]) continue;
alr[uf.leader(i)] = true;
if (first[uf.leader(i)] != -1){
g.addEdge(first[uf.leader(i)],200000);
debug_cnt++;
}else{
g.addEdge(i,200000);
debug_cnt++;
}
}
debug(edges.size()+cnt);
debug(debug_cnt);
HeavyLightDecomposition hld(g,200000);
dsu uf2(200000);
ll A = 0;
ll B = 0;
vl akiyo(200000,0);
vl bkiyo(200000,0);
vl acnt(200000,0);
vl bcnt(200000,0);
vb iscycle(200000,false);
vl X(200000,-1);
vl Y(200000,-1);
vector<ll> first2(200000,-1);
vector<ll> time2(200000,INFL);
lazy_segtree<ll,op,e,ll,mapping,composition,id> sega(200001);
lazy_segtree<ll,op,e,ll,mapping,composition,id> segb(200001);
rep(i,100000){
acnt[i] = 1;
sega.set(hld.toSeq(i),1);
X[i] = i;
Y[i] = i;
bcnt[i+100000] = 1;
segb.set(hld.toSeq(i+100000),1);
X[i+100000] = i+100000;
Y[i+100000] = i+100000;
}
debug("end_init");
rep(i,Q){
auto [a,b] = querys[i];
if(uf2.same(a,b)){
ll l = uf2.leader(a);
if(first2[uf2.leader(a)] == -1){
first2[uf2.leader(a)] = a;
time2[uf2.leader(a)] = i;
}
if(!iscycle[uf2.leader(a)]){
iscycle[l] = true;
A -= akiyo[l];
B -= bkiyo[l];
akiyo[l] = acnt[l];
bkiyo[l] = bcnt[l];
A += akiyo[l];
B += bkiyo[l];
}
ll lca = hld.lca(a,b);
repe(R,hld.path(lca,first2[l],true,false)){
ll tmp = sega.prod(R.l,R.r);
akiyo[l] -= tmp;
A -= tmp;
sega.apply(R.l,R.r,0);
tmp = segb.prod(R.l,R.r);
bkiyo[l] -= tmp;
B -= tmp;
segb.apply(R.l,R.r,0);
}
repe(R,hld.path(lca,b,false,false)){
ll tmp = sega.prod(R.l,R.r);
akiyo[l] -= tmp;
A -= tmp;
sega.apply(R.l,R.r,0);
tmp = segb.prod(R.l,R.r);
bkiyo[l] -= tmp;
B -= tmp;
segb.apply(R.l,R.r,0);
}
}else{
ll la = uf2.leader(a);
ll lb = uf2.leader(b);
debug(i,la,lb);
ll fa = first2[uf2.leader(a)];
ll fb = first2[uf2.leader(b)];
ll ta = time2[uf2.leader(a)];
ll tb = time2[uf2.leader(b)];
ll t;
ll f;
if(time2[uf2.leader(a)] < time2[uf2.leader(b)]){
t = time2[uf2.leader(a)];
f = first2[uf2.leader(a)];
}else{
t = time2[uf2.leader(b)];
f = first2[uf2.leader(b)];
}
uf2.merge(a,b);
first2[uf2.leader(a)] = f;
time2[uf2.leader(a)] = t;
ll newl = uf2.leader(a);
if((!iscycle[la]) && (!iscycle[lb])){
debug(i,la,lb);
A -= akiyo[la];
B -= bkiyo[la];
A -= akiyo[lb];
B -= bkiyo[lb];
acnt[newl] = acnt[la] + acnt[lb];
bcnt[newl] = bcnt[la] + bcnt[lb];
ll x = -1;
ll y = -1;
ll v = -1;
vl tmp = {X[la],X[lb],Y[la],Y[lb]};
repe(l,tmp){
repe(r,tmp){
if (chmax(v,(ll)hld.dist(l,r))){
x = l;
y = r;
}
}
}
X[newl] = x;
Y[newl] = y;
if ((x < 100000) && (y < 100000)){
//同じ色の場合
//必ず長さが偶数のはず。
assert(v%2 == 0);
if((v/2)%2 == 0){
akiyo[newl] = acnt[newl] - 1;
bkiyo[newl] = bcnt[newl];
}else{
akiyo[newl] = acnt[newl];
bkiyo[newl] = bcnt[newl] - 1;
}
}else{
if(!((x >= 100000) && (y >= 100000))){
v--;
}
assert(v%2 == 0);
if((v/2)%2 == 0){
akiyo[newl] = acnt[newl];
bkiyo[newl] = bcnt[newl] - 1;
}else{
akiyo[newl] = acnt[newl] - 1;
bkiyo[newl] = bcnt[newl];
}
}
A += akiyo[newl];
B += bkiyo[newl];
}else if(iscycle[la] && iscycle[lb]){
// faとfbをつなげる
// aと根、bと根をつなげる
akiyo[newl] = akiyo[la] + akiyo[lb];
bkiyo[newl] = bkiyo[la] + bkiyo[lb];
acnt[newl] = acnt[la] + acnt[lb];
bcnt[newl] = bcnt[la] + bcnt[lb];
ll lca = hld.lca(a,b);
repe(R,hld.path(lca,first2[newl],true,false)){
ll tmp = sega.prod(R.l,R.r);
akiyo[newl] -= tmp;
A -= tmp;
sega.apply(R.l,R.r,0);
tmp = segb.prod(R.l,R.r);
bkiyo[newl] -= tmp;
B -= tmp;
segb.apply(R.l,R.r,0);
}
repe(R,hld.path(lca,b,false,false)){
ll tmp = sega.prod(R.l,R.r);
akiyo[newl] -= tmp;
A -= tmp;
sega.apply(R.l,R.r,0);
tmp = segb.prod(R.l,R.r);
bkiyo[newl] -= tmp;
B -= tmp;
segb.apply(R.l,R.r,0);
}
}else{
if(!iscycle[la]){
swap(la,lb);
swap(fa,fb);
swap(ta,tb);
}
// laがサイクル
A -= akiyo[lb];
B -= bkiyo[lb];
akiyo[newl] = akiyo[la] + acnt[lb];
bkiyo[newl] = bkiyo[la] + bcnt[lb];
A += acnt[lb];
B += bcnt[lb];
acnt[newl] = acnt[la] + acnt[lb];
bcnt[newl] = bcnt[la] + bcnt[lb];
}
}
out(A,B);
}
}