信号塔
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

 一切都会逝去，唯有死神永生。

Sppac 国有 n 个基站和 n-1 条街道，第 i 条街道连接两个基站 u_i 和 v_i，保证任意两个基站都可以穿过若干条街道到达彼此。初始每个基站上都有一个信号塔，一条街道上拥有网络覆盖需要满足以下至少一个条件：

  •  此街道直接连接的两个基站上共存在至少一个信号塔。
  •  Sppac 国国王 Capps 居住在此街道。

Sppac 国的居民都居住在街道上，国王 Capps 爱民如子，希望每条街道都有网络覆盖，同时国家经费又十分紧张，所以 Capps 希望拆除尽量多的信号塔，使得每条街道还都有网络覆盖。

请对于每个 i (1\le i \le n-1)，求出当国王 Capps 居住在第 i 条街道时 Sppac 国最多可以拆除多少个信号塔使得每条街道还都有网络覆盖。

输入描述:

本题有多个样例，第一行一个样例数 T (1\le T \le 10^5)。

对于每个样例：

第一行一个整数 n (2\le n \le 2\times 10^5) ，表示 Sppac 国的基站数目。

接下来 n-1 行，第 i 行两个整数 u_i 和 v_i (1\le u_i, v_i \le n, \ u_i \neq v_i)，表示第 i 条街道连接 u_i 基站和 v_i 基站。

保证任意两个基站都可以穿过若干条街道到达彼此。

对于所有样例保证 \sum n \le 2\times 10^5 。

输出描述:

对于每个样例：输出一行 n-1 个整数，第 i 个数表示当国王 Capps 居住在第 i 条街道时 Sppac 国最多可以拆除多少个信号塔使得每条街道还都有网络覆盖，其中相邻整数以一个空格隔开，每行最后一个整数后面不要有额外空格。共输出 T 行。
示例1

输入

复制 
2
5
1 2
2 3
2 4
1 5
6
1 6
5 6
3 5
4 3
2 1

输出

复制 
3 3 3 4
3 4 3 4 4

说明