时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定含 \(n\) 个结点的无根树，有 \(m\) 个人在树上旅行，第 \(i\) 个人从 \(u[i]\) 出发，到 \(v[i]\) 结束。请你统计下面两个信息：

　　1）、经过每个点的人数。

　　2）、经过每条边的人数。

【输入格式】

　　第一行包括两个正整数 \(n,m\)，表示树的节点数和人数，树结点从 1 到 \(n\)编号。
　　接下来 \(n-1\) 行描述树边情况，其中第 \(i\) 行包含 2 个整数 \(a_i, b_i\)，表示第 \(i\) 条双向边连接 \(a_i\) 和 \(b_i\)。注意，边的编号按输入顺序从 \(1..n-1\) 编号。
　　接下来 \(m\) 行描述每个人的旅行信息：\(u[i]\) 和 \(v[i]\)。

【输出格式】

　　第一行包含 \(n\) 个整数，第 \(i\) 个整数表示经过 \(i\) 号点的人数。
　　第二行包含 \(n-1\) 个整数，第 \(i\) 个整数表示编号为经过编号为 \(i\) 的边的人数。

【输入输出样例】

　Input

11 4
1 6
2 1
4 3
6 7
9 8
3 1
3 5
2 10
10 11
8 6
1 9
3 10
11 5
4 8

　Output

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

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n,m≤300000\)

【来源】

　　Mr.he