题目描述

I 国有 $n$ 座城市，这些城市之间通过 $n-1$ 条道路相连。任意两座城市间有且仅有一条简单路径。

你需要为该国规划一套定位系统。这套系统是这样工作的：

• 一些城市中装有恰好一个信号发射器，其他城市中没有信号发射器。
• 定位通过信号接收器完成。在任何一个城市中，信号接收器可以得到自己与每个有信号发射器的城市的距离，进而推断自己所在的城市。不同城市发出的信号对于信号接收器来说是可区分的。

显然，要使这套系统有效，必须满足在任意两个不同的城市中，信号接收器接收到的信号都不完全相同。

你想知道，为了使系统有效，至少需要在多少个城市中安装信号发射器。

I 国的道路一共进行了 $q$ 次翻修。每次翻修会摧毁原来的一条道路，并建设一条新的道路。每次翻修后，任意两座城市间仍然有且仅有一条简单路径。

你需要求出，在第一次翻修前和每次翻修后，至少需要在多少个城市中安装信号发射器。

输入格式

输入数据的第一行包含一个正整数 $n$ ，意义见题目描述。

接下来 $n-1$ 行，每行包含两个数 $u,v$ ，表示初始 $u,v$ 两个城市之间有一条道路。

接下来一行，包含一个正整数 $q$ ，意义见题目描述。

接下来 $q$ 行，每行包含四个正整数 $u,v,x,y$ ，表示 $u,v$ 两个城市之间的道路被摧毁了， $x,y$ 两个城市之间新建了一条道路。

输出格式

输出 $q+1$ 行，第 $i$ 行表示进行 $i-1$ 次翻修后的答案。

样例1

input

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

output

1
2
2
1
1
1

数据范围

对于所有测试数据，保证 $n \le 5 \times 10^5,q \le 10^5$ 。

subtask1(10 pts)：保证 $n,q \le 15$ 。

subtask2(20 pts)：保证 $n,q \le 300$ 。

subtask3(20 pts)：保证 $n,q \le 5000$ 。

subtask4(20 pts)：保证 $n \le 10^5$ 。

subtask5(30 pts)：无特殊限制。