#1759. Let there be rainbows!

内存限制:64 MiB 时间限制:10 Sec

题目描述

个点构成一棵树,开始时任两点之间的边全是灰色的。现决定将已有的边重新涂色,并且是彩虹的颜色。每天将选择两个点点A,B和一种色调C,并A,B之间色调不是C的道路涂成C。现在将具体方案事先告诉你,求输出每种色调被使用了多少次.

输入格式

第一行,一个整数N,点的编号是1~N。 下面若干行,每行两个数A,B,表示A,B之间有道路直接连接。 下面一行,一个整数Q,表示计划的持续天数。 下面Q行,每行三个正整数,S,T,C(1<=S,T<=N,1<=C<=7),表示将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

数据范围与提示