给定 $n$ 个点的树，边按输入顺序编号为 $1,2,...,n-1$，要求作以下操作：

• CHANGE i v ：将第 $i$ 条边权值改为 $v$
• QUERY a b ：询问从 $a$ 点到 $b$ 点路径上的最大边权

有多组测试数据，每组数据以 DONE 结尾。

你被给定一棵 $n$ 个点的带边权的树（边权可以为负）。每个点可能有两种颜色：黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边权值之和。一开始所有的点都是白色的。

要求作以下操作：

• C a 将点a的颜色反转（黑变白，白变黑）

• A 询问 $dist(a,b)$ 的最大值。$a,b$ 点都必须为白色（ $a$ 与 $b$ 可以相同），显然如果树上仍存在白点，查询得到的值一定是个非负数。
  特别地，如果进行 A 操作时树上没有白点，输出 They have disappeared.。

小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

输入长度为 $n$ 的串 $S$ ，求 $S$ 的最长双回文子串 $T$,即可将 $T$ 分为两部分$X$ ， $Y$ ， （ $∣X∣,∣Y∣ \geq 1$ ）且 $X$ 和 $Y$ 都是回文串。

有两个快递员，分别在 $s_1, s_2(0\le s_1,s_2\le 10^9)$ 位置。现在有 $n(1\le n\le 100000)$ 个任务，需要依次完成，每个任务用一个整数 $x_i$ 表示要将货物送到 $x_i$ 位置，让任何一个快递员到 $x_i$ 都可以。

由于快递员之间需要有对讲机联系，请你设计一种方案使得两个快递员之间的最长距离最短。

给定一个长度为 $n$ 的 $01$ 序列，第 $i$ 位是 $0$ 代表 节点 $i$ 到节点 $i \bmod n + 1$ 有一条有向边，第 $i$ 位是 $1$ 代表 节点 $i \bmod n + 1$ 到节点 i 有一条有向边。

我们称一个节点对 $(u,v)$ 是妙的当且仅当不存在 $u$ 到 $v$ 和 $v$ 到 $u$ 的路径任何两者之一。

现在你要从这个图里面挑出一个集合，使得集合中任意两个不同的节点 $u$ 和 $v$ 之间构成的节点对 $(u,v)$ 都是妙的。

请你输出这个集合的大小的最大值。

一棵树上有 $n$ 个节点，把每个节点染成黑色或白色，要求叶子节点一半是黑色，一半是白色（保证叶子节点的个数是偶数）。

求在满足要求的情况下，最小的两端颜色不同的边的数量。

我们定义

请你求出 $J(x) = A$ 有多少个 $x$ 满足条件。

给定一个含有 $n$ 个点， $m$ 条边的森林。有 $q$ 个询问，每次给出两个点 $u_i,v_i$ ，如果 $u_i$ 在联通块 $A$ 内，$v_i$ 在联通块 $B$ 内，我们随机选择两个点 $a \in A,b \in B$ ，我们在 $(a,b)$ 之间连一条边，如果这个连接成后新联通块不构成一个树，输出 $-1$ ，否则输出新联通块树的直径的期望。所有边权均为 $1$ 。

给定 $n$ 个长度均为 $m$ 的字符串，再给出一个 $n$ 行 $m$ 列的矩阵 $\{a _ {nm}\}$。
矩阵元素 $a _ {ij}$ 代表把第 $i$ 个字符串第 $j$ 个字符改成其它任意字符所需要的代价。

现在要求对于任意一个字符串，总存在某一位置 $j$ 使得该位置上的字符在任意其他字符串该位置的字符不同。

即为对于第 x 个字符串 ，有 $\exists j \in [1,m] , \forall i \in [1,n],s _ {xj} \neq s _ {ij}$ 。

求把所有字符串修改成满足上述要求的字符串的最小代价是多少？

数据范围： $1 \le n,m \le 20,1\le a _ {ij} \le 10^6$ 。