Name: Anonymous 2012-11-19 12:41
#include <algorithm>
#include <bitset>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
//#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std ;
#define all(n) n.begin(), n.end()
#define fore(i, n) forn (i, n.size())
#define fori(i, n) for (typeof (n.begin()) i = n.begin() ; i != n.end() ; i++)
#define forn(i, n) forsn (i, 0, n)
#define forsn(i, s, n) for (int i = s ; i < n ; i++)
#define LOG cerr << "[" << __LINE__ << "] "
#define pb push_back
typedef pair <int, int> pii ;
#define y first
#define x second
const int maxn = 10000 ;
const int lmaxn = 15 ;
vector <vector <pii> > M ;
int P[maxn][lmaxn] ;
int H[maxn] ;
int L[maxn] ;
void arbol(int n, int p)
{
/*( ° ¿ °)*/fore(i, M[n]) if (M[n][i].x != p)
/*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*/P[M[n][i].x][0] = n ;
/*( ° ¿ °)*//*( ° ¿ °)*/forsn(u, 1, lmaxn) P[M[n][i].x][u] = P[P[M[n][i].x][u - 1]][u - 1] ;
/*( ° ¿ °)*//*( ° ¿ °)*/H[M[n][i].x] = H[n] + 1 ;
/*( ° ¿ °)*//*( ° ¿ °)*/L[M[n][i].x] = L[n] + M[n][i].y ;
/*( ° ¿ °)*//*( ° ¿ °)*/arbol(M[n][i].x, n) ;
/*( ° ¿ °)*/}
}
int subir(int a, int h)
{
/*( ° ¿ °)*/forn(i, lmaxn) if (h & (1 << i)) a = P[a][i] ;
/*( ° ¿ °)*/return a ;
}
int lca(int a, int b)
{
/*( ° ¿ °)*/if (H[a] > H[b]) swap(a, b) ;
/*( ° ¿ °)*/if (H[a] < H[b]) b = subir(b, H[b] - H[a]) ;
/*( ° ¿ °)*/if (a == b) return a ;
/*( ° ¿ °)*/if (P[a][0] == P[b][0]) return P[a][0] ;
/*( ° ¿ °)*/forsn(i, 1, lmaxn) if (P[a][i] == P[b][i]) return lca(P[a][i - 1], P[b][i - 1]) ;
/*( ° ¿ °)*/return -1 ;
}
int dist(int a, int b)
{
/*( ° ¿ °)*/return L[a] + L[b] - 2 * L[lca(a, b)] ;
}
int kth(int a, int b, int c)
{
/*( ° ¿ °)*/int l = lca(a, b) ;
/*( ° ¿ °)*/if (c <= H[a] - H[l]) return subir(a, c) ;
/*( ° ¿ °)*/return subir(b, H[b] + H[a] - c - 2 * H[l]) ;
}
int main()
{
/*( ° ¿ °)*/int t ; scanf("%d", &t) ;
/*( ° ¿ °)*/forn(z, t)
/*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*/int n ; scanf("%d", &n) ;
/*( ° ¿ °)*//*( ° ¿ °)*/M = vector <vector <pii> > (n) ;
/*( ° ¿ °)*//*( ° ¿ °)*///forn(i, lmaxn) P[0][i] = 0 ;
/*( ° ¿ °)*//*( ° ¿ °)*/H[0] = L[0] = 0 ;
/*( ° ¿ °)*//*( ° ¿ °)*/Q++ ;
/*( ° ¿ °)*//*( ° ¿ °)*/forn(i, n - 1)
/*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/int a, b, c ; scanf("%d %d %d", &a, &b, &c) ; a--, b-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/M[a].pb(pii(c, b)) ; M[b].pb(pii(c, a)) ;
/*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*/arbol(0, -1) ;
/*( ° ¿ °)*//*( ° ¿ °)*/char s[10] ;
/*( ° ¿ °)*//*( ° ¿ °)*/while (scanf("%s", s) && strcmp(s, "DONE"))
/*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/int a, b, c ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/if (!strcmp(s, "DIST"))
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/scanf("%d %d", &a, &b) ; a--, b-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/printf ("%d\n", dist(a, b)) ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/else
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/scanf("%d %d %d", &a, &b, &c) ; a--, b--, c-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/printf("%d\n", kth(a, b, c) + 1) ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*/}
/*( ° ¿ °)*/return 0 ;
}
#include <bitset>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
//#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std ;
#define all(n) n.begin(), n.end()
#define fore(i, n) forn (i, n.size())
#define fori(i, n) for (typeof (n.begin()) i = n.begin() ; i != n.end() ; i++)
#define forn(i, n) forsn (i, 0, n)
#define forsn(i, s, n) for (int i = s ; i < n ; i++)
#define LOG cerr << "[" << __LINE__ << "] "
#define pb push_back
typedef pair <int, int> pii ;
#define y first
#define x second
const int maxn = 10000 ;
const int lmaxn = 15 ;
vector <vector <pii> > M ;
int P[maxn][lmaxn] ;
int H[maxn] ;
int L[maxn] ;
void arbol(int n, int p)
{
/*( ° ¿ °)*/fore(i, M[n]) if (M[n][i].x != p)
/*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*/P[M[n][i].x][0] = n ;
/*( ° ¿ °)*//*( ° ¿ °)*/forsn(u, 1, lmaxn) P[M[n][i].x][u] = P[P[M[n][i].x][u - 1]][u - 1] ;
/*( ° ¿ °)*//*( ° ¿ °)*/H[M[n][i].x] = H[n] + 1 ;
/*( ° ¿ °)*//*( ° ¿ °)*/L[M[n][i].x] = L[n] + M[n][i].y ;
/*( ° ¿ °)*//*( ° ¿ °)*/arbol(M[n][i].x, n) ;
/*( ° ¿ °)*/}
}
int subir(int a, int h)
{
/*( ° ¿ °)*/forn(i, lmaxn) if (h & (1 << i)) a = P[a][i] ;
/*( ° ¿ °)*/return a ;
}
int lca(int a, int b)
{
/*( ° ¿ °)*/if (H[a] > H[b]) swap(a, b) ;
/*( ° ¿ °)*/if (H[a] < H[b]) b = subir(b, H[b] - H[a]) ;
/*( ° ¿ °)*/if (a == b) return a ;
/*( ° ¿ °)*/if (P[a][0] == P[b][0]) return P[a][0] ;
/*( ° ¿ °)*/forsn(i, 1, lmaxn) if (P[a][i] == P[b][i]) return lca(P[a][i - 1], P[b][i - 1]) ;
/*( ° ¿ °)*/return -1 ;
}
int dist(int a, int b)
{
/*( ° ¿ °)*/return L[a] + L[b] - 2 * L[lca(a, b)] ;
}
int kth(int a, int b, int c)
{
/*( ° ¿ °)*/int l = lca(a, b) ;
/*( ° ¿ °)*/if (c <= H[a] - H[l]) return subir(a, c) ;
/*( ° ¿ °)*/return subir(b, H[b] + H[a] - c - 2 * H[l]) ;
}
int main()
{
/*( ° ¿ °)*/int t ; scanf("%d", &t) ;
/*( ° ¿ °)*/forn(z, t)
/*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*/int n ; scanf("%d", &n) ;
/*( ° ¿ °)*//*( ° ¿ °)*/M = vector <vector <pii> > (n) ;
/*( ° ¿ °)*//*( ° ¿ °)*///forn(i, lmaxn) P[0][i] = 0 ;
/*( ° ¿ °)*//*( ° ¿ °)*/H[0] = L[0] = 0 ;
/*( ° ¿ °)*//*( ° ¿ °)*/Q++ ;
/*( ° ¿ °)*//*( ° ¿ °)*/forn(i, n - 1)
/*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/int a, b, c ; scanf("%d %d %d", &a, &b, &c) ; a--, b-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/M[a].pb(pii(c, b)) ; M[b].pb(pii(c, a)) ;
/*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*/arbol(0, -1) ;
/*( ° ¿ °)*//*( ° ¿ °)*/char s[10] ;
/*( ° ¿ °)*//*( ° ¿ °)*/while (scanf("%s", s) && strcmp(s, "DONE"))
/*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/int a, b, c ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/if (!strcmp(s, "DIST"))
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/scanf("%d %d", &a, &b) ; a--, b-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/printf ("%d\n", dist(a, b)) ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/else
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/{
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/scanf("%d %d %d", &a, &b, &c) ; a--, b--, c-- ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/printf("%d\n", kth(a, b, c) + 1) ;
/*( ° ¿ °)*//*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*//*( ° ¿ °)*/}
/*( ° ¿ °)*/}
/*( ° ¿ °)*/return 0 ;
}