색이 있는 트리

처음에는 색이 $C$인 정점 $1$ 하나만 있는 트리가 주어집니다. 이후 두 종류의 연산이 순서대로 $q$개 주어집니다.

• $0$ $x$ $c$ $d$: 색이 $c$인 새 정점을 번호 $(n + 1)$로 트리에 추가합니다. 여기서 $n$은 현재 정점의 개수입니다. 정점 $x$와 $(n + 1)$을 길이가 $d$인 간선으로 잇습니다.
• $1$ $x$ $c$: 정점 $x$의 색을 $c$로 바꿉니다.

각 연산 후에, 현재 트리에서 색이 서로 다른 두 정점 $u$, $v$ ($1 ≤ u, v ≤ n$)를 찾아 두 정점 사이의 거리가 최대가 되도록 해야 합니다.

두 정점 $u$와 $v$의 거리는 트리에서 $u$에서 $v$까지 가는 최단 경로의 길이입니다.

입력에는 여러 개의 테스트 케이스가 들어 있습니다. 첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다. 각 테스트 케이스는 다음과 같습니다.

첫 줄에 연산의 개수 $q$와 정점 $1$의 초기 색 $C$가 주어집니다 ($1 ≤ q ≤ 5 \times 10^5$, $1 ≤ C ≤ q$).

이어지는 $q$개의 줄에는 순서대로 연산이 정수 3개 또는 4개로 주어집니다.

• 줄에 정수 $0$, $x_i$, $c_i$, $d_i$가 주어지면 ($1 ≤ x_i ≤ n$, $1 ≤ c_i ≤ q$, $1 ≤ d_i ≤ 10^9$), 색이 $c_i$인 새 정점 $(n + 1)$을 추가하고 길이 $d_i$인 간선으로 정점 $x_i$와 연결합니다.
• 줄에 정수 $1$, $x_i$, $c_i$가 주어지면 ($1 ≤ x_i ≤ n$, $1 ≤ c_i ≤ q$), 정점 $x_i$의 색을 $c_i$로 바꿉니다.

모든 테스트 케이스의 $q$ 합은 $5 \times 10^5$을 넘지 않습니다.

각 연산 후에, 색이 서로 다른 두 정점 사이 거리의 최댓값을 출력합니다. 그런 쌍이 없으면 대신 $0$을 출력합니다.