Description

给出一棵N 个点的树，每个点有两层，每层有权值和颜色（黑白） 。要求支持以下操作。

1. Cover s t color 将s到t的路径上的点的两层的颜色全部置为 color(0 白1 黑)
2. CVal index layer val 将index号点的 layer 层的权值修改为 val
3. CColor index layer color 将 index号点的 layer 层的颜色修改为 color
4. QMax s t 询问s到 t的路径上的白色最大权值和路径的权值（任意白色层为起点，每

次只能往相同点不同层或者相邻点同一层上移动，每个点的每一层最多走一次，路径经

过的层必须都是白色） ，若 s到 t上的路径没有白点则输出[Bad Request.]

5. QLen s t 询问s到t的路径上的白色最大权值和路径的长度，若 s到 t的路径上没有白

点则输出0

初始树上权值均为 1，颜色均为白色。

N<=5W,Q<=5W,1<=val<=1K,0<=color,layer<=1 所有数据不超过longint范围。 .

Format

Input

第一行一个数N，接下来N*2-2个数s，t，代表s与t之间有连边。第N+1行一个数Q，表示操作数。接下来Q行每行一个操作。

Output

对于每次 QMax，QLen输出对应答案，用换行符分隔。

Samples

6
1 2 2 4 2 5 1 3 3 6
7
CVal 1 0 5
CVal 1 1 3
CColor 1 0 1
CVal 2 0 5
CVal 3 0 3
QMax 5 6
QLen 5 6

17
9