题目描述

有 $N$ 个点构成一棵树，开始时任两点之间的边全是灰色的。现决定将已有的边重新涂色，并且是彩虹的颜色。

每天将选择两个点 $A,B$ 和一种色调 $C$，并将 $A,B$ 之间色调不是 $C$ 的道路涂成 $C$。

现在将具体方案事先告诉你，求输出每种色调被使用了多少次。

输入格式

第一行，一个整数 $N$，点的编号是 $1\sim N$。

下面若干行，每行两个数 $A,B$，表示 $A,B$ 之间有道路直接连接。

下面一行，一个整数 $Q$，表示计划的持续天数。

下面 $Q$ 行，每行三个正整数，$S,T,C$，表示将 $S,T$ 之间颜色不是 $C$ 的道路的颜色都涂成 $C$。

输出格式

共包含 $7$ 行，第 $i$ 行包含一个整数，表示颜色 $i$ 的使用次数。

样例

4
1 2
2 3
3 4
3
1 4 1
2 4 2
1 3 1

4
2
0
0
0
0
0

数据规模与约定

对于 $100\%$ 的数据：$1\leq S,T\leq N\leq 2\times 10^5$，$Q\leq 2\times 10^5$，$1\leq C\leq 7$。

题目来源

IPSC2009