题目描述

大神hkhh给定一棵n个点的边权树，由于他太强了，所以他想考考你。

让你求树中每个子树的最长链是多长？次长链是多长？（链可以长度为零，最长和次长链不能有相同的边）

备注，这里的链是子树中 根到节点的路径长度

输入格式

第一行输入一个T((1<<T)<=2^20)，表示有T组数据

对于每组数据，输入总共n行 。 第一行有两个整数n和S，分别表示总点数和树根。

第2 ~ n行每行有3个整数x,y,z，表示x到y有一条边，边权为z(0<=z<=10000)。

输出格式

输出总共T*2行

对于每组数据，输出两行

第一行输出n个数，第i个数表示以i号点作为根节点的子树的最长链，数之间用2个空格隔开

第二行输出n个数，第i个数表示以i号点作为根节点的子树的次长链，数之间用2个空格隔开

样例数据

input

1
6 3
1 3 999
2 3 1
5 4 23
5 3 1
3 6 1

output

0  0  999  0  23  0
0  0  24  0  0  0

数据规模与约定

%15 n<=10 (这是用来给你们找错误的 --by 良心出题人)

%25 n<=100

%35 n<=500

%45 n<=1000

%55 n<=5000

100% n<=100000