#include
using namespace std;
const int buf_len = 4567;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() {
if (++ bufb == bufe)
bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin);
}
#define readInt(x) {
register int s(0);
do {
readBuf();
} while (!isdigit(*bufb));
do {
s = s * 10 + *bufb - 48;
readBuf();
} while (isdigit(*bufb));
x = s;
}
#define readOpt(x) {
do {
readBuf();
} while (*bufb != ‘G’ && *bufb != ‘C’);
x = *bufb;
}
const int inf = 0x3f3f3f3f;
struct dat { int a, b; dat() {} dat(int ao, int bo) { a = ao, b = bo; } inline int sum() { return (a < 0 || b < 0) ? -inf : (a + b); } inline int amb() { return (a < 0 || b < 0) ? -inf : (a - b); } inline int bma() { return (a < 0 || b < 0) ? -inf : (b - a); } };
inline bool operator ==(const dat& a, const dat& b) { return a. a == b. a && a. b == b. b; } inline bool operator !=(const dat& a, const dat& b) { return a. a != b. a || a. b != b. b; }
struct seg { dat al, ml, ar, mr, wh; int l, r, ans; seg *ls, *rs; inline void update(); inline void init(); }; struct edge { int t; edge *next; };
const int maxn = 100009; const int maxa = 200009; const dat null_dat(-inf, -inf);
int n, m, c[maxn], cnt; int d[maxn], dfb[maxn], dfe[maxn], dfo[maxa]; edge ebuf_arr[maxa], *ebuf(ebuf_arr), *head[maxn]; seg sbuf_arr[maxa * 3], *sbuf(sbuf_arr), *rt;
inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; }
inline dat combDat(const dat& a, const dat& b) { if (a == null_dat || b == null_dat) return null_dat; else if (a. b > b. a) return dat(a. a, a. b - b. a + b. b); else return dat(a. a + b. a - a. b, b. b); }
inline void seg :: update() { register dat tmp; ans = max(ls-> ans, rs-> ans); wh = combDat(ls-> wh, rs-> wh); if (ls-> ar != null_dat && rs-> ml != null_dat) ans = max(ans, combDat(ls-> ar, rs-> ml). sum()); if (ls-> mr != null_dat && rs-> al != null_dat) ans = max(ans, combDat(ls-> mr, rs-> al). sum()); //update al al = ls-> al; if (al. sum() < (tmp = combDat(ls-> wh, rs-> al)). sum()) al = tmp; if (al. sum() < (tmp = combDat(ls-> wh, rs-> ml)). sum()) al = tmp; //update ml ml = ls-> ml; if (ml. bma() < (tmp = combDat(ls-> wh, rs-> al)). bma()) ml = tmp; if (ml. bma() < (tmp = combDat(ls-> wh, rs-> ml)). bma()) ml = tmp; //update ar ar = rs-> ar; if (ar. sum() < (tmp = combDat(ls-> ar, rs-> wh)). sum()) ar = tmp; if (ar. sum() < (tmp = combDat(ls-> mr, rs-> wh)). sum()) ar = tmp; //update mr mr = rs-> mr; if (mr. amb() < (tmp = combDat(ls-> ar, rs-> wh)). amb()) mr = tmp; if (mr. amb() < (tmp = combDat(ls-> mr, rs-> wh)). amb()) mr = tmp; }
inline void seg :: init() { if (dfo[l - 1] > 0 && !c[dfo[l - 1]]) { if (dfo[l] > 0) ar = mr = dat(0, 1); else ar = mr = dat(1, 0); } else { ar = mr = null_dat; } if (dfo[l] > 0 && !c[dfo[l]]) al = ml = dat(0, 1); else al = ml = null_dat; if (al != null_dat && ar != null_dat) ans = 1; else ans = -inf; }
#define midp ((p->l+p->r)»1) inline seg* sgtBuild(int l, int r) { seg *p(sbuf ++); p-> l = l; p-> r = r; if (p-> l + 1 == p-> r) { if (dfo[p-> l] < 0) p-> wh = dat(1, 0); else p-> wh = dat(0, 1); p-> init(); } else { p-> ls = sgtBuild(l, midp); p-> rs = sgtBuild(midp, r); p-> update(); } return p; }
inline void sgtUpd(seg* p, int po) { if (p-> l + 1 == p-> r) { p-> init(); } else { if (po < midp) sgtUpd(p-> ls, po); else sgtUpd(p-> rs, po); p-> update(); } }
void build() { static int stc[maxn], stv[maxn]; int tsc(1), tsv(0), dfn(0); memset(d, 0, sizeof(d)); d[stc[1] = 1] = 1; while (tsc) { int u(stc[tsc –]); for (; tsv && d[stv[tsv]] >= d[u]; – tsv) dfo[dfe[stv[tsv]] = ++ dfn] = -stv[tsv]; stv[++ tsv] = dfo[dfb[u] = ++ dfn] = u; for (edge* e = head[u]; e; e = e-> next) if (!d[e-> t]) { d[e-> t] = d[u] + 1; stc[++ tsc] = e-> t; } } for (; tsv; – tsv) dfo[dfe[stv[tsv]] = ++ dfn] = -stv[tsv]; rt = sgtBuild(1, n * 2 + 1); }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
readInt(n);
cnt = n;
c[0] = 1;
memset(head, 0, sizeof(head));
for (int i = 1; i < n; ++ i) {
int u, v;
readInt(u);
readInt(v);
addEdge(u, v);
addEdge(v, u);
}
build();
readInt(m);
while (m --) {
char opt;
readOpt(opt);
if (opt == 'G') {
if (cnt == 0)
puts("-1");
else if (cnt == 1)
puts("0");
else
printf("%d\n", rt-> ans);
}
else {
int u;
readInt(u);
if (c[u])
++ cnt;
else
-- cnt;
c[u] ^= 1;
sgtUpd(rt, dfb[u]);
sgtUpd(rt, dfb[u] + 1);
sgtUpd(rt, dfe[u]);
if (dfe[u] < n * 2)
sgtUpd(rt, dfe[u] + 1);
}
}
}