#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
using namespace std;
struct Node {
Node *left, *right, *father;
int val, key, sum;
} *root, *sentinel;
// Must call initTree before using splay tree
void initTree() {
sentinel = new Node;
sentinel -> left = sentinel -> right = sentinel -> father = sentinel;
sentinel -> val = 0;
sentinel -> key = sentinel -> sum = 0;
}
void setLink(Node *x, Node *y, bool left) {
if (left) x -> left = y;
else x -> right = y;
y -> father = x;
}
void update(Node *x) {
x -> sum = x->key + x->left->sum + x->right->sum;
}
void upTree(Node *x) {
Node *y = x -> father;
Node *z = y -> father;
Node *tmp;
if (y->right == x) {
tmp = x -> left;
setLink(x, y, true);
setLink(y, tmp, false);
}
else {
tmp = x -> right;
setLink(x, y, false);
setLink(y, tmp, true);
}
setLink(z, x, z->left == y);
update(y); update(x);
}
void splay(Node *x) {
while (1) {
Node *y = x -> father;
if (y == sentinel) return ;
Node *z = y -> father;
if (z != sentinel) {
if ((z->right == y) == (y->right == x)) upTree(y);
else upTree(x);
}
upTree(x);
}
}
Node *join(Node *t1, Node *t2) {
if (t1 == sentinel) return t2;
if (t2 == sentinel) return t1;
while (1) {
// refine(t1); // Used for range cover
if (t1 -> right == sentinel) break;
t1 = t1 -> right;
}
splay(t1);
setLink(t1, t2, false);
update(t1);
return t1;
}
const int MN = 200111;
int n, a[MN], father[MN], sign[MN], cur;
vector< int > ke[MN];
Node *nodes[MN], *first[MN], *last[MN];
Node *createTree(int l, int r) {
if (l > r) return sentinel;
int mid = (l + r) >> 1;
Node *res = new Node;
res->left = res->right = res->father = sentinel;
res->val = a[mid];
res->key = res->sum = sign[mid];
Node *left = createTree(l, mid - 1);
Node *right = createTree(mid+1, r);
if (left != sentinel) setLink(res, left, true);
if (right != sentinel) setLink(res, right, false);
update(res);
return res;
}
Node *access(Node *root, int k) {
if (root->left->sum >= k) return access(root->left, k);
k -= root->left->sum;
if (k == 1 && root->key == 1) return root;
k -= root->key;
return access(root->right, k);
}
void init() {
FOR(i,1,n) {
ke[i].clear();
first[i] = last[i] = sentinel;
}
cur = 0;
}
void dfs(int u) {
++cur; a[cur] = u; sign[cur] = 1;
REP(i,ke[u].size()) {
int v = ke[u][i];
father[v] = u;
dfs(v);
}
++cur; a[cur] = u; sign[cur] = 0;
}
void visitTree(Node *x, string pref = "") {
if (x == sentinel) return ;
visitTree(x->left, pref + " ");
cout << pref << x->val << ' ' << x->key << ' ' << x->sum << endl;
visitTree(x->right, pref + " ");
}
#define printTree(x) { cout << #x << ":" << endl; visitTree(x); }
void visit(Node *p) {
if (p == sentinel) return ;
visit(p->left);
visit(p->right);
if (p->key) first[p->val] = p;
else last[p->val] = p;
}
int main() {
int ntest; cin >> ntest;
while (ntest--) {
cin >> n;
initTree();
init();
FOR(i,2,n) {
int u, v; cin >> u >> v;
ke[u].push_back(v);
}
dfs(1);
// PR(a, n+n);
root = createTree(1, n+n);
// printTree(root);
visit(root);
// FOR(i,1,n) cout << first[i]->val << ' '; cout << endl;
// FOR(i,1,n) cout << last[i]->val << ' '; cout << endl;
int q; cin >> q;
while (q--) {
// cout << "q = " << q << endl;
// cerr << q << endl;
int typ; cin >> typ;
if (typ == 1) {
int u, v; cin >> u >> v;
// cout << typ << ' ' << u << ' ' << v << endl;
// First, split into 3 parts: [leftmost, first(u)) [first(u), last(u)] and (last[u], rightmost]
Node *t2 = first[u]; splay(t2);
Node *t1 = t2->left;
t2->left = t1->father = sentinel;
update(t2);
t2 = last[u]; splay(t2);
Node *t3 = t2->right;
t2->right = t3->father = sentinel;
update(t2);
// printTree(t1);
// printTree(t2);
// printTree(t3);
t1 = join(t1, t3);
// Split t1 into 2 parts
Node *t4 = last[v]; splay(t4);
Node *t5 = t4->left;
t4->left = t5->father = sentinel;
update(t4);
// printTree(t4);
// printTree(t5);
root = join(t5, t2);
root = join(root, t4);
// printTree(root);
} else {
int k; cin >> k;
// cout << typ << ' ' << k << endl;
Node *t = access(root, k);
splay(t);
root = t;
// printTree(root);
cout << t->val << endl;
}
// cout << "q = " << q << endl;
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHZlY3Rvcj4KCiNkZWZpbmUgRk9SKGksYSxiKSBmb3IoaW50IGk9KGEpLF9iPShiKTsgaSA8PSBfYjsgKytpKQojZGVmaW5lIFJFUChpLGEpIGZvcihpbnQgaT0wLF9hPShhKTsgaSA8IF9hOyArK2kpCgojZGVmaW5lIFBSKGEsbikgeyBjb3V0IDw8ICNhIDw8ICIgPSAiOyBGT1IoXywxLG4pIGNvdXQgPDwgYVtfXSA8PCAnICc7IGNvdXQgPDwgZW5kbDsgfQp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IE5vZGUgewogICAgTm9kZSAqbGVmdCwgKnJpZ2h0LCAqZmF0aGVyOwogICAgaW50IHZhbCwga2V5LCBzdW07Cn0gKnJvb3QsICpzZW50aW5lbDsKCi8vIE11c3QgY2FsbCBpbml0VHJlZSBiZWZvcmUgdXNpbmcgc3BsYXkgdHJlZQp2b2lkIGluaXRUcmVlKCkgewogICAgc2VudGluZWwgPSBuZXcgTm9kZTsKICAgIHNlbnRpbmVsIC0+IGxlZnQgPSBzZW50aW5lbCAtPiByaWdodCA9IHNlbnRpbmVsIC0+IGZhdGhlciA9IHNlbnRpbmVsOwogICAgc2VudGluZWwgLT4gdmFsID0gMDsKICAgIHNlbnRpbmVsIC0+IGtleSA9IHNlbnRpbmVsIC0+IHN1bSA9IDA7Cn0Kdm9pZCBzZXRMaW5rKE5vZGUgKngsIE5vZGUgKnksIGJvb2wgbGVmdCkgewogICAgaWYgKGxlZnQpIHggLT4gbGVmdCA9IHk7CiAgICBlbHNlIHggLT4gcmlnaHQgPSB5OwogICAgeSAtPiBmYXRoZXIgPSB4Owp9CnZvaWQgdXBkYXRlKE5vZGUgKngpIHsKICAgIHggLT4gc3VtID0geC0+a2V5ICsgeC0+bGVmdC0+c3VtICsgeC0+cmlnaHQtPnN1bTsKfQp2b2lkIHVwVHJlZShOb2RlICp4KSB7CiAgICBOb2RlICp5ID0geCAtPiBmYXRoZXI7CiAgICBOb2RlICp6ID0geSAtPiBmYXRoZXI7CiAgICBOb2RlICp0bXA7CiAgICBpZiAoeS0+cmlnaHQgPT0geCkgewogICAgICAgIHRtcCA9IHggLT4gbGVmdDsKICAgICAgICBzZXRMaW5rKHgsIHksIHRydWUpOwogICAgICAgIHNldExpbmsoeSwgdG1wLCBmYWxzZSk7CiAgICB9CiAgICBlbHNlIHsKICAgICAgICB0bXAgPSB4IC0+IHJpZ2h0OwogICAgICAgIHNldExpbmsoeCwgeSwgZmFsc2UpOwogICAgICAgIHNldExpbmsoeSwgdG1wLCB0cnVlKTsKICAgIH0KICAgIHNldExpbmsoeiwgeCwgei0+bGVmdCA9PSB5KTsKICAgIHVwZGF0ZSh5KTsgdXBkYXRlKHgpOwp9CnZvaWQgc3BsYXkoTm9kZSAqeCkgewogICAgd2hpbGUgKDEpIHsKICAgICAgICBOb2RlICp5ID0geCAtPiBmYXRoZXI7CiAgICAgICAgaWYgKHkgPT0gc2VudGluZWwpIHJldHVybiA7CiAgICAgICAgTm9kZSAqeiA9IHkgLT4gZmF0aGVyOwogICAgICAgIGlmICh6ICE9IHNlbnRpbmVsKSB7CiAgICAgICAgICAgIGlmICgoei0+cmlnaHQgPT0geSkgPT0gKHktPnJpZ2h0ID09IHgpKSB1cFRyZWUoeSk7CiAgICAgICAgICAgIGVsc2UgdXBUcmVlKHgpOwogICAgICAgIH0KICAgICAgICB1cFRyZWUoeCk7CiAgICB9Cn0KTm9kZSAqam9pbihOb2RlICp0MSwgTm9kZSAqdDIpIHsKICAgIGlmICh0MSA9PSBzZW50aW5lbCkgcmV0dXJuIHQyOwogICAgaWYgKHQyID09IHNlbnRpbmVsKSByZXR1cm4gdDE7CiAgICB3aGlsZSAoMSkgewogICAgICAgIC8vIHJlZmluZSh0MSk7IC8vIFVzZWQgZm9yIHJhbmdlIGNvdmVyCiAgICAgICAgaWYgKHQxIC0+IHJpZ2h0ID09IHNlbnRpbmVsKSBicmVhazsKICAgICAgICB0MSA9IHQxIC0+IHJpZ2h0OwogICAgfQogICAgc3BsYXkodDEpOwogICAgc2V0TGluayh0MSwgdDIsIGZhbHNlKTsKICAgIHVwZGF0ZSh0MSk7CiAgICByZXR1cm4gdDE7Cn0KCmNvbnN0IGludCBNTiA9IDIwMDExMTsKaW50IG4sIGFbTU5dLCBmYXRoZXJbTU5dLCBzaWduW01OXSwgY3VyOwp2ZWN0b3I8IGludCA+IGtlW01OXTsKTm9kZSAqbm9kZXNbTU5dLCAqZmlyc3RbTU5dLCAqbGFzdFtNTl07CgpOb2RlICpjcmVhdGVUcmVlKGludCBsLCBpbnQgcikgewogICAgaWYgKGwgPiByKSByZXR1cm4gc2VudGluZWw7CiAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgTm9kZSAqcmVzID0gbmV3IE5vZGU7CiAgICByZXMtPmxlZnQgPSByZXMtPnJpZ2h0ID0gcmVzLT5mYXRoZXIgPSBzZW50aW5lbDsKICAgIHJlcy0+dmFsID0gYVttaWRdOwogICAgcmVzLT5rZXkgPSByZXMtPnN1bSA9IHNpZ25bbWlkXTsKCiAgICBOb2RlICpsZWZ0ID0gY3JlYXRlVHJlZShsLCBtaWQgLSAxKTsKICAgIE5vZGUgKnJpZ2h0ID0gY3JlYXRlVHJlZShtaWQrMSwgcik7CgogICAgaWYgKGxlZnQgIT0gc2VudGluZWwpIHNldExpbmsocmVzLCBsZWZ0LCB0cnVlKTsKICAgIGlmIChyaWdodCAhPSBzZW50aW5lbCkgc2V0TGluayhyZXMsIHJpZ2h0LCBmYWxzZSk7CgogICAgdXBkYXRlKHJlcyk7CiAgICByZXR1cm4gcmVzOwp9CgpOb2RlICphY2Nlc3MoTm9kZSAqcm9vdCwgaW50IGspIHsKICAgIGlmIChyb290LT5sZWZ0LT5zdW0gPj0gaykgcmV0dXJuIGFjY2Vzcyhyb290LT5sZWZ0LCBrKTsKICAgIGsgLT0gcm9vdC0+bGVmdC0+c3VtOwogICAgaWYgKGsgPT0gMSAmJiByb290LT5rZXkgPT0gMSkgcmV0dXJuIHJvb3Q7CiAgICBrIC09IHJvb3QtPmtleTsKCiAgICByZXR1cm4gYWNjZXNzKHJvb3QtPnJpZ2h0LCBrKTsKfQoKdm9pZCBpbml0KCkgewogICAgRk9SKGksMSxuKSB7CiAgICAgICAga2VbaV0uY2xlYXIoKTsKICAgICAgICBmaXJzdFtpXSA9IGxhc3RbaV0gPSBzZW50aW5lbDsKICAgIH0KICAgIGN1ciA9IDA7Cn0KCnZvaWQgZGZzKGludCB1KSB7CiAgICArK2N1cjsgYVtjdXJdID0gdTsgc2lnbltjdXJdID0gMTsKICAgIFJFUChpLGtlW3VdLnNpemUoKSkgewogICAgICAgIGludCB2ID0ga2VbdV1baV07CiAgICAgICAgZmF0aGVyW3ZdID0gdTsKICAgICAgICBkZnModik7CiAgICB9CiAgICArK2N1cjsgYVtjdXJdID0gdTsgc2lnbltjdXJdID0gMDsKfQoKdm9pZCB2aXNpdFRyZWUoTm9kZSAqeCwgc3RyaW5nIHByZWYgPSAiIikgewogICAgaWYgKHggPT0gc2VudGluZWwpIHJldHVybiA7CiAgICB2aXNpdFRyZWUoeC0+bGVmdCwgcHJlZiArICIgICIpOwogICAgY291dCA8PCBwcmVmIDw8IHgtPnZhbCA8PCAnICcgPDwgeC0+a2V5IDw8ICcgJyA8PCB4LT5zdW0gPDwgZW5kbDsKICAgIHZpc2l0VHJlZSh4LT5yaWdodCwgcHJlZiArICIgICIpOwp9CgojZGVmaW5lIHByaW50VHJlZSh4KSAgeyBjb3V0IDw8ICN4IDw8ICI6IiA8PCBlbmRsOyB2aXNpdFRyZWUoeCk7IH0KCnZvaWQgdmlzaXQoTm9kZSAqcCkgewogICAgaWYgKHAgPT0gc2VudGluZWwpIHJldHVybiA7CgogICAgdmlzaXQocC0+bGVmdCk7CiAgICB2aXNpdChwLT5yaWdodCk7CgogICAgaWYgKHAtPmtleSkgZmlyc3RbcC0+dmFsXSA9IHA7CiAgICBlbHNlIGxhc3RbcC0+dmFsXSA9IHA7Cn0KCmludCBtYWluKCkgewogICAgaW50IG50ZXN0OyBjaW4gPj4gbnRlc3Q7CiAgICB3aGlsZSAobnRlc3QtLSkgewogICAgICAgIGNpbiA+PiBuOwogICAgICAgIGluaXRUcmVlKCk7CiAgICAgICAgaW5pdCgpOwogICAgICAgIEZPUihpLDIsbikgewogICAgICAgICAgICBpbnQgdSwgdjsgY2luID4+IHUgPj4gdjsKICAgICAgICAgICAga2VbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgIH0KICAgICAgICBkZnMoMSk7CiAgICAgICAgLy8gUFIoYSwgbituKTsKCiAgICAgICAgcm9vdCA9IGNyZWF0ZVRyZWUoMSwgbituKTsKICAgICAgICAvLyBwcmludFRyZWUocm9vdCk7CgogICAgICAgIHZpc2l0KHJvb3QpOwoKICAgICAgICAvLyBGT1IoaSwxLG4pIGNvdXQgPDwgZmlyc3RbaV0tPnZhbCA8PCAnICc7IGNvdXQgPDwgZW5kbDsKICAgICAgICAvLyBGT1IoaSwxLG4pIGNvdXQgPDwgbGFzdFtpXS0+dmFsIDw8ICcgJzsgY291dCA8PCBlbmRsOwoKICAgICAgICBpbnQgcTsgY2luID4+IHE7CiAgICAgICAgd2hpbGUgKHEtLSkgewogICAgICAgICAgICAvLyBjb3V0IDw8ICJxID0gIiA8PCBxIDw8IGVuZGw7CiAgICAgICAgICAgIC8vIGNlcnIgPDwgcSA8PCBlbmRsOwogICAgICAgICAgICBpbnQgdHlwOyBjaW4gPj4gdHlwOwogICAgICAgICAgICBpZiAodHlwID09IDEpIHsKICAgICAgICAgICAgICAgIGludCB1LCB2OyBjaW4gPj4gdSA+PiB2OwogICAgICAgICAgICAgICAgLy8gY291dCA8PCB0eXAgPDwgJyAnIDw8IHUgPDwgJyAnIDw8IHYgPDwgZW5kbDsKICAgICAgICAgICAgICAgIC8vIEZpcnN0LCBzcGxpdCBpbnRvIDMgcGFydHM6IFtsZWZ0bW9zdCwgZmlyc3QodSkpIFtmaXJzdCh1KSwgbGFzdCh1KV0gYW5kIChsYXN0W3VdLCByaWdodG1vc3RdCiAgICAgICAgICAgICAgICBOb2RlICp0MiA9IGZpcnN0W3VdOyBzcGxheSh0Mik7CiAgICAgICAgICAgICAgICBOb2RlICp0MSA9IHQyLT5sZWZ0OwogICAgICAgICAgICAgICAgdDItPmxlZnQgPSB0MS0+ZmF0aGVyID0gc2VudGluZWw7CiAgICAgICAgICAgICAgICB1cGRhdGUodDIpOwoKICAgICAgICAgICAgICAgIHQyID0gbGFzdFt1XTsgc3BsYXkodDIpOwogICAgICAgICAgICAgICAgTm9kZSAqdDMgPSB0Mi0+cmlnaHQ7CiAgICAgICAgICAgICAgICB0Mi0+cmlnaHQgPSB0My0+ZmF0aGVyID0gc2VudGluZWw7CiAgICAgICAgICAgICAgICB1cGRhdGUodDIpOwoKICAgICAgICAgICAgICAgIC8vIHByaW50VHJlZSh0MSk7CiAgICAgICAgICAgICAgICAvLyBwcmludFRyZWUodDIpOwogICAgICAgICAgICAgICAgLy8gcHJpbnRUcmVlKHQzKTsKCiAgICAgICAgICAgICAgICB0MSA9IGpvaW4odDEsIHQzKTsKCiAgICAgICAgICAgICAgICAvLyBTcGxpdCB0MSBpbnRvIDIgcGFydHMKICAgICAgICAgICAgICAgIE5vZGUgKnQ0ID0gbGFzdFt2XTsgc3BsYXkodDQpOwogICAgICAgICAgICAgICAgTm9kZSAqdDUgPSB0NC0+bGVmdDsKICAgICAgICAgICAgICAgIHQ0LT5sZWZ0ID0gdDUtPmZhdGhlciA9IHNlbnRpbmVsOwogICAgICAgICAgICAgICAgdXBkYXRlKHQ0KTsKCiAgICAgICAgICAgICAgICAvLyBwcmludFRyZWUodDQpOwogICAgICAgICAgICAgICAgLy8gcHJpbnRUcmVlKHQ1KTsKCiAgICAgICAgICAgICAgICByb290ID0gam9pbih0NSwgdDIpOwogICAgICAgICAgICAgICAgcm9vdCA9IGpvaW4ocm9vdCwgdDQpOwoKICAgICAgICAgICAgICAgIC8vIHByaW50VHJlZShyb290KTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGludCBrOyBjaW4gPj4gazsKICAgICAgICAgICAgICAgIC8vIGNvdXQgPDwgdHlwIDw8ICcgJyA8PCBrIDw8IGVuZGw7CiAgICAgICAgICAgICAgICBOb2RlICp0ID0gYWNjZXNzKHJvb3QsIGspOwogICAgICAgICAgICAgICAgc3BsYXkodCk7CiAgICAgICAgICAgICAgICByb290ID0gdDsKICAgICAgICAgICAgICAgIC8vIHByaW50VHJlZShyb290KTsKICAgICAgICAgICAgICAgIGNvdXQgPDwgdC0+dmFsIDw8IGVuZGw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgLy8gY291dCA8PCAicSA9ICIgPDwgcSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9