Background

The Constraints here differ slightly from SPOJ.

Problem Description

You are given a tree with $n$ nodes, where each edge has a weight. Initially, all nodes are white. There are two types of operations:

• C x: toggle the color of node $x$; white becomes black, and black becomes white.
• A: query the distance between the farthest two white nodes in the tree. These two white nodes may coincide (in which case the distance is $0$).

Input Format

The first line contains a positive integer $n$ ($n \le 10^5$).

Each of the next $n-1$ lines contains three integers $a$, $b$, $c$, representing an edge between nodes $a$ and $b$ with weight $c$ ($|c| \le 10^3$).

The next line contains a positive integer $q$ ($q \le 2\times 10^5$), the number of operations.

Each of the next $q$ lines contains one operation.

Output Format

For each A operation, if there are no white nodes in the tree, output a line with the string They have disappeared.. Otherwise, output a line with one integer, the distance between the farthest two white nodes in the tree.

3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A

2
2
0
They have disappeared.

Hint

Translated by ChatGPT 5