#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>#include<algorithm>using namespace std;const int maxn = 111111;struct Node{    int next; int to;}e[maxn * 2];int len;int z;int size[maxn], son[maxn], father[maxn], deep[maxn], pos[maxn], top[maxn], vis[maxn], color[maxn];int head[maxn], val[maxn];inline bool scanf_(int &ret) {    char c; int sgn;    if (c = getchar(), c == EOF) return 0; //EOF    while (c != ‘-‘ && (c<‘0‘ || c>‘9‘)) c = getchar();    sgn = (c == ‘-‘) ? -1 : 1;    ret = (c == ‘-‘) ? 0 : (c - ‘0‘);    while (c = getchar(), c >= ‘0‘&&c <= ‘9‘) ret = ret * 10 + (c - ‘0‘);    ret *= sgn;    return 1;}inline void printf_(int x) {    if (x>9) printf_(x / 10);    putchar(x % 10 + ‘0‘);}void add(int from, int to){    e[len].to = to;    e[len].next = head[from];    head[from] = len++;}void init(int x){    size[x] = 1; son[x] = 0;    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x]) continue;        father[cc] = x;        deep[cc] = deep[x] + 1;        init(cc);        size[x] += size[cc];        if (size[son[x]]<size[cc]) son[x] = cc;    }}void dfs(int x, int tp){    pos[x] = ++z; vis[z] = x; top[x] = tp;    if (son[x]) dfs(son[x], tp);    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x] || cc == son[x]) continue;        dfs(cc, cc);    }}void gao(int x, int y, int add){    int fx = top[x]; int fy = top[y];    while (fx != fy){        if (deep[fx]<deep[fy]){            swap(x, y); swap(fx, fy);        }        color[pos[fx]] += add; color[pos[x] + 1] -= add;        x = father[fx]; fx = top[x];    }    if (deep[x]>deep[y]) swap(x, y);    color[pos[x]] += add; color[pos[y] + 1] -= add;}int color1[maxn];void gao1(int x, int y, int add){    int fx = top[x]; int fy = top[y];    while (fx != fy){        if (deep[fx]<deep[fy]){            swap(x, y); swap(fx, fy);        }        color1[pos[fx]] += add; color1[pos[x] + 1] -= add;        x = father[fx]; fx = top[x];    }    if (x == y) return;    if (deep[x]>deep[y]) swap(x, y);    color1[pos[son[x]]] += add; color1[pos[y] + 1] -= add;}int ans[maxn];char str[100];int edge[maxn][2];int main(){    int __size__ = 256 << 20;    char * __p__ = (char *)malloc(__size__) + __size__;    __asm__("movl %0,%%esp\n"::"r"(__p__));    int T, n, m;    int a, b, c;    scanf_(T);    int Icase = 0;    while (T--){        printf("Case #%d:\n", ++Icase);        scanf_(n); scanf_(m);        len = 0; z = 0;        memset(head, -1, sizeof(head));        memset(color, 0, sizeof(color));        memset(val, 0, sizeof(val));        memset(color1, 0, sizeof(color1));        for (int i = 0; i<n - 1; i++){            scanf_(edge[i][0]); scanf_(edge[i][1]);            add(edge[i][0], edge[i][1]); add(edge[i][1], edge[i][0]);        }        father[1] = 1;        init(1); dfs(1, 1);        for (int i = 0; i<n - 1; i++){            a = edge[i][0]; b = edge[i][1];            if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]);            ans[i] = pos[edge[i][1]];        }        for (int i = 0; i<m; i++){            scanf("%s", str);            scanf_(a); scanf_(b); scanf_(c);            if (strcmp(str, "ADD1") == 0){                gao(a, b, c);            }            else gao1(a, b, c);        }        for (int i = 1; i <= n; i++) color[i] += color[i - 1];        for (int i = 1; i <= n; i++) color1[i] += color1[i - 1];        for (int i = 1; i <= n; i++){            int t = vis[i];            val[t] = color[i];        }        printf_(val[1]);        for (int i = 2; i <= n; i++){            putchar(‘ ‘);            printf_(val[i]);        }        cout << endl;        for (int i = 0; i<n - 1; i++){            if (i) putchar(‘ ‘);            int t = ans[i];            printf_(color1[t]);        }        cout << endl;    }    return 0;}