#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define F first
#define S second
#define tm lkjsdaf
const int MAXN = 1e5 + 10;
const int LOG = 17;
int n, q;
vector<pii> adj[MAXN];
int cntEdge[MAXN][2], cntVertices;
int par[LOG][MAXN], parColor[MAXN], sub[MAXN], depth[MAXN];
bool cmpEdges(pii e1, pii e2){return sub[e1.F] > sub[e2.F];}
//------------HLD Prep
int heavyPar[MAXN], heavyChild[MAXN];
int dfsInitHld(int v, int p = -1, int pc = -1){
par[0][v] = p, parColor[v] = pc;
depth[v] = (p==-1? 0: depth[p]+1);
if (~p)
adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(p, pc)));
sub[v] = 1;
for (auto e:adj[v])
sub[v] += dfsInitHld(e.F, v, e.S);
sort(adj[v].begin(), adj[v].end(), cmpEdges);
return sub[v];
}
int hldRoot[MAXN], st[MAXN], ft[MAXN], tm, ord[MAXN];
void dfsBuildHld(int v, int rt = -1){
heavyPar[v] = heavyChild[v] = -1;
ord[tm] = v;
st[v] = tm++;
if (rt == -1)
rt = v;
else
heavyPar[v] = par[0][v], cntEdge[v][parColor[v]]--;
hldRoot[v] = rt;
for (auto e:adj[v]) {
if (rt != -1) {
heavyChild[v] = e.F;
cntEdge[v][parColor[e.F]]--;
}
dfsBuildHld(e.F, rt);
rt = -1;
}
ft[v] = tm;
}
//------------LCA
void preLca(){
for (int w = 1; w < LOG; w++)
for (int v = 0; v < n; v++)
if (par[w-1][v] == -1)
par[w][v] = -1;
else
par[w][v] = par[w-1][par[w-1][v]];
}
int lca(int u, int v){
if (depth[u] < depth[v])
swap(u, v);
for (int w = LOG-1; ~w; w--)
if (depth[u] - (1<<w) >= depth[v])
u = par[w][u];
if (u == v) return u;
for (int w = LOG-1; ~w; w--)
if (par[w][u] ^ par[w][v])
u = par[w][u], v = par[w][v];
return par[0][u];
}
//-----------Edge Segment
int edgeSeg[MAXN<<2];
int getEdgeColor(int v, int b, int e, int pos, int cur = 0){
cur ^= edgeSeg[v];
if (e - b == 1)
return parColor[ord[pos]]^cur;
int mid = b + e >> 1;
return pos < mid? getEdgeColor(v<<1, b, mid, pos, cur): getEdgeColor(v<<1^1, mid, e, pos, cur);
}
void changeColor(int v, int b, int e, int l, int r){
if (l <= b && e <= r){
edgeSeg[v]^=1;
return;
}
if (r <= b || e <= l) return;
int mid = b + e >> 1;
changeColor(v<<1, b, mid, l, r);
changeColor(v<<1^1, mid, e, l, r);
}
//-------------Main Segment
int tempCol[2][2];
void fillTempCol(int v, int t){
if (~heavyChild[v])
tempCol[t][getEdgeColor(1, 0, n, st[heavyChild[v]])]++;
if (~heavyPar[v])
tempCol[t][getEdgeColor(1, 0, n, st[v])]++;
}
int cnt[3][MAXN<<2], lz[MAXN<<2];
int getGoodVertices(int v, int b, int e, int l, int r){
if (l <= b && e <= r) return cnt[1][v] + cnt[2][v];
if (r <= b || e <= l) return 0;
int mid = b + e >> 1;
return getGoodVertices(v<<1, b, mid, l, r) + getGoodVertices(v<<1^1, mid, e, l, r);
}
void pushDown(int v){
if (!lz[v]) return;
for (int i = 0; i < 2; i++){
lz[v<<1^i] ^= 1;
swap(cnt[0][v<<1^i], cnt[1][v<<1^i]);
}
lz[v] = 0;
}
void merge(int v){
for (int w = 0; w < 3; w++)
cnt[w][v] = cnt[w][v<<1] + cnt[w][v<<1^1];
}
void flip(int v, int b, int e, int l, int r){
if (l <= b && e <= r){
lz[v]^=1;
swap(cnt[0][v], cnt[1][v]);
return;
}
if (r <= b || e <= l) return;
int mid = b + e >> 1;
pushDown(v);
flip(v<<1, b, mid, l, r);
flip(v<<1^1, mid, e, l, r);
merge(v);
}
void setPos(int v, int u, int z = -1){
for (int w = 0; w < 3; w++)
cnt[w][v] = 0;
if (cntEdge[u][0] > 0 && cntEdge[u][1] > 0) return;
if (z == -1){
memset(tempCol, 0, sizeof(tempCol));
fillTempCol(u, 0);
z = 0;
}
if (tempCol[0][0] > 0 && tempCol[0][1] > 0) return;
if (cntEdge[u][0] + cntEdge[u][1] == 0 || tempCol[0][0] + tempCol[0][1] == 0)
cnt[2][v] = 1;
else if ((cntEdge[u][0] > 0 && tempCol[0][0] > 0) || (cntEdge[u][1] > 0 && tempCol[0][1] > 0))
cnt[1][v] = 1;
else
cnt[0][v] = 1;
}
void updatePos(int v, int b, int e, int pos, int z = -1){
if (e - b == 1){
setPos(v, ord[b], z);
return;
}
int mid = b + e >> 1;
pushDown(v);
if (pos < mid)
updatePos(v<<1, b, mid, pos);
else
updatePos(v<<1^1, mid, e, pos);
merge(v);
}
void plantMainSeg(int v, int b, int e){
lz[v] = 0;
if (e - b == 1){
setPos(v, ord[b]);
return;
}
int mid = b + e >> 1;
plantMainSeg(v<<1, b, mid);
plantMainSeg(v<<1^1, mid, e);
merge(v);
}
//-------------Handling Query
void dealWithHeavyPath(int v, int p){
if (v == p) return;
memset(tempCol, 0, sizeof(tempCol));
fillTempCol(v, 0);
fillTempCol(p, 1);
if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices--;
if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices--;
changeColor(1, 0, n, st[p]+1, st[v]+1);
memset(tempCol, 0, sizeof(tempCol));
fillTempCol(v, 0);
fillTempCol(p, 1);
if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices++;
if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices++;
if (hldRoot[v] != v && adj[v].size())
updatePos(1, 0, n, st[v], 0);
if (hldRoot[p] != p)
updatePos(1, 0, n, st[p], 1);
if (depth[v]-1 > depth[p]){//There's a real path to deal with
cntVertices -= getGoodVertices(1, 0, n, st[p]+1, st[v]);
flip(1, 0, n, st[p]+1, st[v]);
cntVertices += getGoodVertices(1, 0, n, st[p]+1, st[v]);
}
}
void dealWithLightEdge(int v){
int p = par[0][v];
memset(tempCol, 0, sizeof(tempCol));
fillTempCol(v, 0);
fillTempCol(p, 1);
if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices--;
if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices--;
cntEdge[v][parColor[v]]--;
cntEdge[p][parColor[v]]--;
parColor[v] ^= 1;
cntEdge[v][parColor[v]]++;
cntEdge[p][parColor[v]]++;
if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices++;
if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices++;
//updatePos(1, 0, n, st[v], 0);
if (hldRoot[p] != p)
updatePos(1, 0, n, st[p], 1);
}
void dealWith(int v, int p){
if (v == p) return;
while (depth[v] > depth[p]){
int rt = hldRoot[v];
if (depth[rt] < depth[p]) rt = p;
dealWithHeavyPath(v, rt);
v = rt;
if (v == p) break;
dealWithLightEdge(v);
v = par[0][v];
}
}
void debug(int v, int b, int e){
cout << v << " " << b << " " << e << " ";
for (int w = 0; w < 3; w++)
cout << cnt[w][v] << " ";
cout << lz[v] << " ";
cout << endl;
if (e - b == 1) return;
int mid = b + e >> 1;
pushDown(v);
debug(v<<1, b, mid);
debug(v<<1^1, mid, e);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
cin >> n;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n-1; i++){
int a, b, c; cin >> a >> b >> c, a--, b--;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
cntVertices = 0;
for (int v = 0; v < n; v++){
cntEdge[v][0] = cntEdge[v][1] = 0;
for (auto e:adj[v])
cntEdge[v][e.S]++;
cntVertices += int(cntEdge[v][0]==0 || cntEdge[v][1]==0);
}
dfsInitHld(0);
preLca();
tm = 0;
dfsBuildHld(0);
fill(edgeSeg, edgeSeg + 4*(n+2), 0);
plantMainSeg(1, 0, n);
int q; cin >> q;
while (q--){
int u, v; cin >> u >> v, u--, v--;
int p = lca(u, v);
// debug(1, 0, n);
dealWith(u, p);
dealWith(v, p);
cout << 1 + (n - cntVertices) << "\n";
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgdG0gbGtqc2RhZgoKY29uc3QgaW50IE1BWE4gPSAxZTUgKyAxMDsKY29uc3QgaW50IExPRyA9IDE3OwoKaW50IG4sIHE7CnZlY3RvcjxwaWk+IGFkaltNQVhOXTsKaW50IGNudEVkZ2VbTUFYTl1bMl0sIGNudFZlcnRpY2VzOwoKaW50IHBhcltMT0ddW01BWE5dLCBwYXJDb2xvcltNQVhOXSwgc3ViW01BWE5dLCBkZXB0aFtNQVhOXTsKYm9vbCBjbXBFZGdlcyhwaWkgZTEsIHBpaSBlMil7cmV0dXJuIHN1YltlMS5GXSA+IHN1YltlMi5GXTt9CgovLy0tLS0tLS0tLS0tLUhMRCBQcmVwCgppbnQgaGVhdnlQYXJbTUFYTl0sIGhlYXZ5Q2hpbGRbTUFYTl07CmludCBkZnNJbml0SGxkKGludCB2LCBpbnQgcCA9IC0xLCBpbnQgcGMgPSAtMSl7CglwYXJbMF1bdl0gPSBwLCBwYXJDb2xvclt2XSA9IHBjOwoJZGVwdGhbdl0gPSAocD09LTE/IDA6IGRlcHRoW3BdKzEpOwoJaWYgKH5wKQoJCWFkalt2XS5lcmFzZShmaW5kKGFkalt2XS5iZWdpbigpLCBhZGpbdl0uZW5kKCksIG1ha2VfcGFpcihwLCBwYykpKTsKCglzdWJbdl0gPSAxOwoJZm9yIChhdXRvIGU6YWRqW3ZdKQoJCXN1Ylt2XSArPSBkZnNJbml0SGxkKGUuRiwgdiwgZS5TKTsKCglzb3J0KGFkalt2XS5iZWdpbigpLCBhZGpbdl0uZW5kKCksIGNtcEVkZ2VzKTsKCXJldHVybiBzdWJbdl07Cn0KCmludCBobGRSb290W01BWE5dLCBzdFtNQVhOXSwgZnRbTUFYTl0sIHRtLCBvcmRbTUFYTl07CnZvaWQgZGZzQnVpbGRIbGQoaW50IHYsIGludCBydCA9IC0xKXsKCWhlYXZ5UGFyW3ZdID0gaGVhdnlDaGlsZFt2XSA9IC0xOwoKCW9yZFt0bV0gPSB2OwoJc3Rbdl0gPSB0bSsrOwoJaWYgKHJ0ID09IC0xKQoJCXJ0ID0gdjsKCWVsc2UKCQloZWF2eVBhclt2XSA9IHBhclswXVt2XSwgY250RWRnZVt2XVtwYXJDb2xvclt2XV0tLTsKCWhsZFJvb3Rbdl0gPSBydDsKCglmb3IgKGF1dG8gZTphZGpbdl0pIHsKCQlpZiAocnQgIT0gLTEpIHsKCQkJaGVhdnlDaGlsZFt2XSA9IGUuRjsKCQkJY250RWRnZVt2XVtwYXJDb2xvcltlLkZdXS0tOwoJCX0KCQlkZnNCdWlsZEhsZChlLkYsIHJ0KTsKCQlydCA9IC0xOwoJfQoKCWZ0W3ZdID0gdG07Cn0KCgoKLy8tLS0tLS0tLS0tLS1MQ0EKCnZvaWQgcHJlTGNhKCl7Cglmb3IgKGludCB3ID0gMTsgdyA8IExPRzsgdysrKQoJCWZvciAoaW50IHYgPSAwOyB2IDwgbjsgdisrKQoJCQlpZiAocGFyW3ctMV1bdl0gPT0gLTEpCgkJCQlwYXJbd11bdl0gPSAtMTsKCQkJZWxzZQoJCQkJcGFyW3ddW3ZdID0gcGFyW3ctMV1bcGFyW3ctMV1bdl1dOwp9CgppbnQgbGNhKGludCB1LCBpbnQgdil7CglpZiAoZGVwdGhbdV0gPCBkZXB0aFt2XSkgCgkJc3dhcCh1LCB2KTsKCWZvciAoaW50IHcgPSBMT0ctMTsgfnc7IHctLSkKCQlpZiAoZGVwdGhbdV0gLSAoMTw8dykgPj0gZGVwdGhbdl0pCgkJCXUgPSBwYXJbd11bdV07CglpZiAodSA9PSB2KSByZXR1cm4gdTsKCglmb3IgKGludCB3ID0gTE9HLTE7IH53OyB3LS0pCgkJaWYgKHBhclt3XVt1XSBeIHBhclt3XVt2XSkKCQkJdSA9IHBhclt3XVt1XSwgdiA9IHBhclt3XVt2XTsKCXJldHVybiBwYXJbMF1bdV07Cn0KCgoKLy8tLS0tLS0tLS0tLUVkZ2UgU2VnbWVudAoKaW50IGVkZ2VTZWdbTUFYTjw8Ml07CmludCBnZXRFZGdlQ29sb3IoaW50IHYsIGludCBiLCBpbnQgZSwgaW50IHBvcywgaW50IGN1ciA9IDApewoJY3VyIF49IGVkZ2VTZWdbdl07CglpZiAoZSAtIGIgPT0gMSkKCQlyZXR1cm4gcGFyQ29sb3Jbb3JkW3Bvc11dXmN1cjsKCglpbnQgbWlkID0gYiArIGUgPj4gMTsKCXJldHVybiBwb3MgPCBtaWQ/IGdldEVkZ2VDb2xvcih2PDwxLCBiLCBtaWQsIHBvcywgY3VyKTogZ2V0RWRnZUNvbG9yKHY8PDFeMSwgbWlkLCBlLCBwb3MsIGN1cik7Cn0KCnZvaWQgY2hhbmdlQ29sb3IoaW50IHYsIGludCBiLCBpbnQgZSwgaW50IGwsIGludCByKXsKCWlmIChsIDw9IGIgJiYgZSA8PSByKXsKCQllZGdlU2VnW3ZdXj0xOwoJCXJldHVybjsKCX0KCWlmIChyIDw9IGIgfHwgZSA8PSBsKSByZXR1cm47CgoJaW50IG1pZCA9IGIgKyBlID4+IDE7CgljaGFuZ2VDb2xvcih2PDwxLCBiLCBtaWQsIGwsIHIpOwoJY2hhbmdlQ29sb3Iodjw8MV4xLCBtaWQsIGUsIGwsIHIpOwp9CgoKLy8tLS0tLS0tLS0tLS0tTWFpbiBTZWdtZW50CmludCB0ZW1wQ29sWzJdWzJdOwp2b2lkIGZpbGxUZW1wQ29sKGludCB2LCBpbnQgdCl7CglpZiAofmhlYXZ5Q2hpbGRbdl0pCgkJdGVtcENvbFt0XVtnZXRFZGdlQ29sb3IoMSwgMCwgbiwgc3RbaGVhdnlDaGlsZFt2XV0pXSsrOwoJaWYgKH5oZWF2eVBhclt2XSkKCQl0ZW1wQ29sW3RdW2dldEVkZ2VDb2xvcigxLCAwLCBuLCBzdFt2XSldKys7Cn0KCmludCBjbnRbM11bTUFYTjw8Ml0sIGx6W01BWE48PDJdOwppbnQgZ2V0R29vZFZlcnRpY2VzKGludCB2LCBpbnQgYiwgaW50IGUsIGludCBsLCBpbnQgcil7CglpZiAobCA8PSBiICYmIGUgPD0gcikgcmV0dXJuIGNudFsxXVt2XSArIGNudFsyXVt2XTsKCWlmIChyIDw9IGIgfHwgZSA8PSBsKSByZXR1cm4gMDsKCglpbnQgbWlkID0gYiArIGUgPj4gMTsKCXJldHVybiBnZXRHb29kVmVydGljZXModjw8MSwgYiwgbWlkLCBsLCByKSArIGdldEdvb2RWZXJ0aWNlcyh2PDwxXjEsIG1pZCwgZSwgbCwgcik7Cn0KCnZvaWQgcHVzaERvd24oaW50IHYpewoJaWYgKCFselt2XSkgcmV0dXJuOwoKCWZvciAoaW50IGkgPSAwOyBpIDwgMjsgaSsrKXsKCQlselt2PDwxXmldIF49IDE7CgkJc3dhcChjbnRbMF1bdjw8MV5pXSwgY250WzFdW3Y8PDFeaV0pOwoJfQoKCWx6W3ZdID0gMDsKfQoKdm9pZCBtZXJnZShpbnQgdil7Cglmb3IgKGludCB3ID0gMDsgdyA8IDM7IHcrKykKCQljbnRbd11bdl0gPSBjbnRbd11bdjw8MV0gKyBjbnRbd11bdjw8MV4xXTsKfQoKdm9pZCBmbGlwKGludCB2LCBpbnQgYiwgaW50IGUsIGludCBsLCBpbnQgcil7CglpZiAobCA8PSBiICYmIGUgPD0gcil7CgkJbHpbdl1ePTE7CgkJc3dhcChjbnRbMF1bdl0sIGNudFsxXVt2XSk7CgkJcmV0dXJuOwoJfQoJaWYgKHIgPD0gYiB8fCBlIDw9IGwpIHJldHVybjsKCglpbnQgbWlkID0gYiArIGUgPj4gMTsKCXB1c2hEb3duKHYpOwoJZmxpcCh2PDwxLCBiLCBtaWQsIGwsIHIpOwoJZmxpcCh2PDwxXjEsIG1pZCwgZSwgbCwgcik7CgltZXJnZSh2KTsKfQoKdm9pZCBzZXRQb3MoaW50IHYsIGludCB1LCBpbnQgeiA9IC0xKXsKCWZvciAoaW50IHcgPSAwOyB3IDwgMzsgdysrKQoJCWNudFt3XVt2XSA9IDA7CglpZiAoY250RWRnZVt1XVswXSA+IDAgJiYgY250RWRnZVt1XVsxXSA+IDApIHJldHVybjsKCglpZiAoeiA9PSAtMSl7CgkJbWVtc2V0KHRlbXBDb2wsIDAsIHNpemVvZih0ZW1wQ29sKSk7CgkJZmlsbFRlbXBDb2wodSwgMCk7CgkJeiA9IDA7Cgl9CgoJaWYgKHRlbXBDb2xbMF1bMF0gPiAwICYmIHRlbXBDb2xbMF1bMV0gPiAwKSByZXR1cm47CglpZiAoY250RWRnZVt1XVswXSArIGNudEVkZ2VbdV1bMV0gPT0gMCB8fCB0ZW1wQ29sWzBdWzBdICsgdGVtcENvbFswXVsxXSA9PSAwKQoJCWNudFsyXVt2XSA9IDE7CgllbHNlIGlmICgoY250RWRnZVt1XVswXSA+IDAgJiYgdGVtcENvbFswXVswXSA+IDApIHx8IChjbnRFZGdlW3VdWzFdID4gMCAmJiB0ZW1wQ29sWzBdWzFdID4gMCkpCgkJY250WzFdW3ZdID0gMTsKCWVsc2UKCQljbnRbMF1bdl0gPSAxOwp9Cgp2b2lkIHVwZGF0ZVBvcyhpbnQgdiwgaW50IGIsIGludCBlLCBpbnQgcG9zLCBpbnQgeiA9IC0xKXsKCWlmIChlIC0gYiA9PSAxKXsKCQlzZXRQb3Modiwgb3JkW2JdLCB6KTsKCQlyZXR1cm47Cgl9CgoJaW50IG1pZCA9IGIgKyBlID4+IDE7CglwdXNoRG93bih2KTsKCWlmIChwb3MgPCBtaWQpCgkJdXBkYXRlUG9zKHY8PDEsIGIsIG1pZCwgcG9zKTsKCWVsc2UKCQl1cGRhdGVQb3Modjw8MV4xLCBtaWQsIGUsIHBvcyk7CgltZXJnZSh2KTsKfQoKdm9pZCBwbGFudE1haW5TZWcoaW50IHYsIGludCBiLCBpbnQgZSl7Cglselt2XSA9IDA7CglpZiAoZSAtIGIgPT0gMSl7CgkJc2V0UG9zKHYsIG9yZFtiXSk7CgkJcmV0dXJuOwoJfQoKCWludCBtaWQgPSBiICsgZSA+PiAxOwoJcGxhbnRNYWluU2VnKHY8PDEsIGIsIG1pZCk7CglwbGFudE1haW5TZWcodjw8MV4xLCBtaWQsIGUpOwoJbWVyZ2Uodik7Cn0KCi8vLS0tLS0tLS0tLS0tLUhhbmRsaW5nIFF1ZXJ5Cgp2b2lkIGRlYWxXaXRoSGVhdnlQYXRoKGludCB2LCBpbnQgcCl7CglpZiAodiA9PSBwKSByZXR1cm47CgoJbWVtc2V0KHRlbXBDb2wsIDAsIHNpemVvZih0ZW1wQ29sKSk7CglmaWxsVGVtcENvbCh2LCAwKTsKCWZpbGxUZW1wQ29sKHAsIDEpOwoJaWYgKGNudEVkZ2Vbdl1bMF0gKyB0ZW1wQ29sWzBdWzBdID09IDAgfHwgY250RWRnZVt2XVsxXSArIHRlbXBDb2xbMF1bMV0gPT0gMCkgY250VmVydGljZXMtLTsKCWlmIChjbnRFZGdlW3BdWzBdICsgdGVtcENvbFsxXVswXSA9PSAwIHx8IGNudEVkZ2VbcF1bMV0gKyB0ZW1wQ29sWzFdWzFdID09IDApIGNudFZlcnRpY2VzLS07CgkKCWNoYW5nZUNvbG9yKDEsIDAsIG4sIHN0W3BdKzEsIHN0W3ZdKzEpOwoKCW1lbXNldCh0ZW1wQ29sLCAwLCBzaXplb2YodGVtcENvbCkpOwoJZmlsbFRlbXBDb2wodiwgMCk7CglmaWxsVGVtcENvbChwLCAxKTsKCWlmIChjbnRFZGdlW3ZdWzBdICsgdGVtcENvbFswXVswXSA9PSAwIHx8IGNudEVkZ2Vbdl1bMV0gKyB0ZW1wQ29sWzBdWzFdID09IDApIGNudFZlcnRpY2VzKys7CglpZiAoY250RWRnZVtwXVswXSArIHRlbXBDb2xbMV1bMF0gPT0gMCB8fCBjbnRFZGdlW3BdWzFdICsgdGVtcENvbFsxXVsxXSA9PSAwKSBjbnRWZXJ0aWNlcysrOwoJaWYgKGhsZFJvb3Rbdl0gIT0gdiAmJiBhZGpbdl0uc2l6ZSgpKQoJCXVwZGF0ZVBvcygxLCAwLCBuLCBzdFt2XSwgMCk7CglpZiAoaGxkUm9vdFtwXSAhPSBwKQoJCXVwZGF0ZVBvcygxLCAwLCBuLCBzdFtwXSwgMSk7CgoJaWYgKGRlcHRoW3ZdLTEgPiBkZXB0aFtwXSl7Ly9UaGVyZSdzIGEgcmVhbCBwYXRoIHRvIGRlYWwgd2l0aAoJCWNudFZlcnRpY2VzIC09IGdldEdvb2RWZXJ0aWNlcygxLCAwLCBuLCBzdFtwXSsxLCBzdFt2XSk7CgkJZmxpcCgxLCAwLCBuLCBzdFtwXSsxLCBzdFt2XSk7CgkJY250VmVydGljZXMgKz0gZ2V0R29vZFZlcnRpY2VzKDEsIDAsIG4sIHN0W3BdKzEsIHN0W3ZdKTsKCX0KfQoKdm9pZCBkZWFsV2l0aExpZ2h0RWRnZShpbnQgdil7CglpbnQgcCA9IHBhclswXVt2XTsKCW1lbXNldCh0ZW1wQ29sLCAwLCBzaXplb2YodGVtcENvbCkpOwoJZmlsbFRlbXBDb2wodiwgMCk7CglmaWxsVGVtcENvbChwLCAxKTsKCglpZiAoY250RWRnZVt2XVswXSArIHRlbXBDb2xbMF1bMF0gPT0gMCB8fCBjbnRFZGdlW3ZdWzFdICsgdGVtcENvbFswXVsxXSA9PSAwKSBjbnRWZXJ0aWNlcy0tOwoJaWYgKGNudEVkZ2VbcF1bMF0gKyB0ZW1wQ29sWzFdWzBdID09IDAgfHwgY250RWRnZVtwXVsxXSArIHRlbXBDb2xbMV1bMV0gPT0gMCkgY250VmVydGljZXMtLTsKCgljbnRFZGdlW3ZdW3BhckNvbG9yW3ZdXS0tOwoJY250RWRnZVtwXVtwYXJDb2xvclt2XV0tLTsKCglwYXJDb2xvclt2XSBePSAxOwoKCWNudEVkZ2Vbdl1bcGFyQ29sb3Jbdl1dKys7CgljbnRFZGdlW3BdW3BhckNvbG9yW3ZdXSsrOwoJaWYgKGNudEVkZ2Vbdl1bMF0gKyB0ZW1wQ29sWzBdWzBdID09IDAgfHwgY250RWRnZVt2XVsxXSArIHRlbXBDb2xbMF1bMV0gPT0gMCkgY250VmVydGljZXMrKzsKCWlmIChjbnRFZGdlW3BdWzBdICsgdGVtcENvbFsxXVswXSA9PSAwIHx8IGNudEVkZ2VbcF1bMV0gKyB0ZW1wQ29sWzFdWzFdID09IDApIGNudFZlcnRpY2VzKys7CgkvL3VwZGF0ZVBvcygxLCAwLCBuLCBzdFt2XSwgMCk7CglpZiAoaGxkUm9vdFtwXSAhPSBwKQoJCXVwZGF0ZVBvcygxLCAwLCBuLCBzdFtwXSwgMSk7Cn0KCnZvaWQgZGVhbFdpdGgoaW50IHYsIGludCBwKXsKCWlmICh2ID09IHApIHJldHVybjsKCQoJd2hpbGUgKGRlcHRoW3ZdID4gZGVwdGhbcF0pewoJCWludCBydCA9IGhsZFJvb3Rbdl07CgkJaWYgKGRlcHRoW3J0XSA8IGRlcHRoW3BdKSBydCA9IHA7CgkJZGVhbFdpdGhIZWF2eVBhdGgodiwgcnQpOwoKCQl2ID0gcnQ7CgkJaWYgKHYgPT0gcCkgYnJlYWs7CgkJZGVhbFdpdGhMaWdodEVkZ2Uodik7CgkJdiA9IHBhclswXVt2XTsKCX0KfQoKdm9pZCBkZWJ1ZyhpbnQgdiwgaW50IGIsIGludCBlKXsKCWNvdXQgPDwgdiA8PCAiICAiIDw8IGIgPDwgIiAiIDw8IGUgPDwgIiAgICAgICI7Cglmb3IgKGludCB3ID0gMDsgdyA8IDM7IHcrKykKCQljb3V0IDw8IGNudFt3XVt2XSA8PCAiICI7Cgljb3V0IDw8IGx6W3ZdIDw8ICIgIjsKCWNvdXQgPDwgZW5kbDsKCglpZiAoZSAtIGIgPT0gMSkgcmV0dXJuOwoKCWludCBtaWQgPSBiICsgZSA+PiAxOwoJcHVzaERvd24odik7CglkZWJ1Zyh2PDwxLCBiLCBtaWQpOwoJZGVidWcodjw8MV4xLCBtaWQsIGUpOwp9CgppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoMCk7CglpbnQgdGU7CWNpbiA+PiB0ZTsKCXdoaWxlICh0ZS0tKXsKCQljaW4gPj4gbjsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgYWRqW2ldLmNsZWFyKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuLTE7IGkrKyl7CgkJCWludCBhLCBiLCBjOyBjaW4gPj4gYSA+PiBiID4+IGMsIGEtLSwgYi0tOwoJCQlhZGpbYV0ucHVzaF9iYWNrKHtiLCBjfSk7CgkJCWFkaltiXS5wdXNoX2JhY2soe2EsIGN9KTsKCQl9CgkJY250VmVydGljZXMgPSAwOwoJCWZvciAoaW50IHYgPSAwOyB2IDwgbjsgdisrKXsKCQkJY250RWRnZVt2XVswXSA9IGNudEVkZ2Vbdl1bMV0gPSAwOwoJCQlmb3IgKGF1dG8gZTphZGpbdl0pCgkJCQljbnRFZGdlW3ZdW2UuU10rKzsKCQkJY250VmVydGljZXMgKz0gaW50KGNudEVkZ2Vbdl1bMF09PTAgfHwgY250RWRnZVt2XVsxXT09MCk7CgkJfQoJCWRmc0luaXRIbGQoMCk7CgkJcHJlTGNhKCk7CgkJdG0gPSAwOwoJCWRmc0J1aWxkSGxkKDApOwoJCWZpbGwoZWRnZVNlZywgZWRnZVNlZyArIDQqKG4rMiksIDApOwoKCQlwbGFudE1haW5TZWcoMSwgMCwgbik7CgoJCWludCBxOyBjaW4gPj4gcTsKCQl3aGlsZSAocS0tKXsKCQkJaW50IHUsIHY7IGNpbiA+PiB1ID4+IHYsIHUtLSwgdi0tOwoJCQlpbnQgcCA9IGxjYSh1LCB2KTsKCS8vCQlkZWJ1ZygxLCAwLCBuKTsKCQkJZGVhbFdpdGgodSwgcCk7CgkJCWRlYWxXaXRoKHYsIHApOwoJCQljb3V0IDw8IDEgKyAobiAtIGNudFZlcnRpY2VzKSA8PCAiXG4iOwoJCX0KCX0KCXJldHVybiAwOwp9