#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define sz(x) (int) (x).size()

const int BUF_SZ = 1 << 15;
inline namespace Input {
	char buf[BUF_SZ];int pos;int len;
	char next_char() {
	if (pos == len) {pos = 0;
	len = (int)fread(buf, 1, BUF_SZ, stdin);
	if (!len) { return EOF; }}
	return buf[pos++];}
	int read_int() {
	int x;char ch;int sgn = 1;
	while (!isdigit(ch = next_char())) {
	if (ch == '-') { sgn *= -1; }}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;}
}
inline namespace Output {
	char buf[BUF_SZ];int pos;
	void flush_out() {fwrite(buf, 1, pos, stdout);pos = 0;}
	void write_char(char c) {
	if (pos == BUF_SZ) { flush_out(); }
	buf[pos++] = c;}
	void write_int(int x) {
	static char num_buf[100];
	if (x < 0) {write_char('-');x *= -1;}
	int len = 0;
	for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
	write_char((char)('0' + x));
	while (len) { write_char(num_buf[--len]); }
	write_char('\n');}
	void init_output() { assert(atexit(flush_out) == 0); }
}

const int inf=9;

struct sparsemin { vector<int> a; int h; vector<vector<int>> st; sparsemin() {} sparsemin(vector<int>& arr) : a(arr), h(log2(a.size()) + 1), st(h + 1) { for (int i = 0; i < a.size(); i++) st[0].push_back(i); for (int i = 1; i <= h; i++) for (int j = 0; j + (1 << i) <= arr.size(); j++) st[i].push_back(a[st[i-1][j]] < a[st[i-1][j + (1 << (i-1))]] ? st[i-1][j] : st[i-1][j + (1 << (i-1))]); } int rmq(int l, int r) { int i = log2(r - l + 1); return a[st[i][l]] < a[st[i][r - (1 << i) + 1]] ? st[i][l] : st[i][r - (1 << i) + 1]; } };
struct tree {
    int n; vector<vector<array<int,2>>> adj; vector<int> par, etour, tin, tot, dep, dtour; sparsemin st;
    tree() {}
    void init(int n1) { adj.resize(0); par.resize(0); etour.resize(0); tin.resize(0); tot.resize(0); dep.resize(0); dtour.resize(0); n = n1; adj.resize(n); }
    void add_edge(int u, int v, int w = 1) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); }
    void go() { par.resize(n); tin.resize(n); tot.resize(n); dep.resize(n); dfs(0, 0, 0); for (int i = 0; i < etour.size(); i++) dtour.push_back(dep[etour[i]]); st = sparsemin(dtour); }
    void dfs(int v, int p, int d) { par[v] = p, dep[v] = d; tin[v] = etour.size(); etour.push_back(v); for (auto e : adj[v]) { int i = e[0], w = e[1]; if (i == p) continue; dfs(i, v, d + w); etour.push_back(v); } tot[v] = etour.size(); etour.push_back(v); }
    int lca(int l, int r) { int mnv = min(tin[l], tin[r]); int mxv = max(tin[l], tin[r]); return etour[st.rmq(mnv, mxv)]; }
    int dist(int u, int v) { if (u==-1 || v==-1) {return 0;} return dep[u] + dep[v] - dep[lca(u, v)]; }
};

const int mxn=5e5+5;

int n,q,c[mxn],qr[mxn][4],np;
tree t;

void chmax(int &x, int &y, int x1, int y1) {
	if (x==-1 || y==-1) {
		x=x1, y=y1;
		return;
	}
	if (x1==-1 || y1==-1) {
		return;
	}
	if (t.dist(x1,y1)>=t.dist(x,y)) {
		x=x1;
		y=y1;
	}
}

vector<int> aux;

struct node {
	node *l=0,*r=0;
	int lo,hi;
	int x=-1,y=-1,xd=-1,yd=-1;
	node() {
		x=-1,y=-1,xd=-1,yd=-1;
	}
	node(int i) {x=i,y=i,lo=i,hi=i;}
	node(int lo,int hi) : lo(lo),hi(hi) {
		x=-1,y=-1,xd=-1,yd=-1;
	}
	void push() {
		if (!l) {
			l = new node(lo,(lo+hi)/2);
			r = new node((lo+hi)/2+1,hi);
		}
	}
	void pull() {
		if (!l) return;
		x=-1,y=-1;
		aux = {l->x,l->y,r->x,r->y};
		for (int i=0; i<sz(aux); i++) {
			for (int j=i; j<sz(aux); j++) {
				chmax(x,y,aux[i],aux[j]);
			}
		}
		xd=-1,yd=-1;
		aux = {l->x,l->y,r->x,r->y,l->xd,l->yd,r->xd,r->yd};
		for (int i=0; i<sz(aux); i++) {
			for (int j=i+1; j<sz(aux); j++) {
				if (aux[i]!=-1 && aux[j]!=-1 && c[aux[i]] != c[aux[j]]) {
					chmax(xd,yd,aux[i],aux[j]);
				}
			}
		}
	}
	void point_set(int I, int X, int Y) {
		if (lo==I && I==hi) {
			x=X, y=Y;
			if (X!=-1 && Y!=-1 && c[X] != c[Y]) {
				xd=X,yd=Y;
			} else {
				xd=-1,yd=-1;
			}
			return;
		}
		if (lo>I || hi<I) return;
		push();
		if (I<=(lo+hi)/2) l->point_set(I,X,Y);
		else r->point_set(I,X,Y);
		pull();
	}
};

node crt[mxn], trt;

void solve() {
	q = read_int();
	c[0] = read_int();
	n = 0;
	t.init(q+5);
	np=1;
	for (int i=0; i<q; i++) {
		qr[i][0] = read_int();
		qr[i][1] = read_int();
		qr[i][2] = read_int();
		if (!qr[i][0]) {
			int d = read_int();
			t.add_edge(qr[i][1]-1,np++,d);
			n++;
			qr[i][1]=np;
		}
		qr[i][1]--;
	}
	t.go();
	for (int i=0; i<=q; i++) {
		crt[i] = node(0,mxn);
	}
	trt = node(0,mxn);
	crt[c[0]].point_set(0,0,0);
	trt.point_set(c[0],crt[c[0]].x,crt[c[0]].y);
	for (int i=0; i<q; i++) {
		int tr=qr[i][0],x=qr[i][1],ci=qr[i][2];
		int pcx = c[x];
		c[x] = ci;
		if (tr) {
			crt[pcx].point_set(x,-1,-1);
			trt.point_set(pcx,crt[pcx].x,crt[pcx].y);
		}

		crt[ci].point_set(x,x,x);
		trt.point_set(ci,crt[ci].x,crt[ci].y);
		write_int(t.dist(trt.xd,trt.yd));
	}
}

signed main() {
	init_output();

	int t = read_int();
	while (t--) {
		solve();
	}

	return 0;
}