4445. 饭团

【题目描述】

机房里有一棵蜜雪树，树上每个节点都生活着一只果蝇，并储存着一种饭团。由于每天都有神秘人馈赠，每个节点的饭团都是无限的。每只果蝇都能吃到子树内的所有饭团。

一天，果蝇王来到机房，决定让每只果蝇都吃到子树外的所有饭团。它可以进行以下操作：

- 指定 $x$，获取 $x$ 节点的饭团。

- 撤回上一次获取操作。

- 指定 $x$，把手上的每种饭团都拿一个给 $x$ 上的果蝇，注意此时手上的饭团必须恰好来自 $x$ 子树外的所有点，该操作并不会改变当前拥有的饭团种类。

果蝇王希望让每个果蝇都吃到子树外的饭团。帮帮它！

【输入格式】

第一行一个数 $T$，表示测试数据组数。

对于每组测试数据：

- 首先一行一个数 $n$，表示节点数。

- 接下来 $n-1$ 行，每行两个数表示树边。

【输出格式】

对于每组测试数据，输出一行。

对于操作一，输出 $+x$，$x$ 为要获取的节点。

对于操作二，输出 $-$。

对于操作三，输出 $=x$，$x$ 为要给饭团的节点。

当操作结束后，输出一个字符 $!$，接着换行。

行内所有字符间不允许有空格。

当已有一个节点的饭团时，不允许再对其进行一操作。

当手上没有饭团时，不允许进行二操作。

必须对每个点进行恰好一次三操作。

【样例输入】

1
6
1 2
3 1
4 2
3 6
5 3

【样例输出】

=1+1+3+5+6=2+2=4----+4+2=3+3+6=5-+5=6!

【数据规模与约定】

对于 10% 的数据，树是一条链。

对于另 10% 的数据，树是以 $1$ 为根的菊花。

对于另 20% 的数据，$n\le 2000$。

对于所有数据，$1\le n\le 10^5$，$1\le T\le 3$。

对于每组测试数据，最多进行 $4.5\times 10^6$ 次一操作。

大样例

【来源】

luogu P7124