暂无测试数据。

题目描述

蒜头君有一棵有 $n$ 个点的有根树，节点编号从 1 到 $n$，根节点编号为 $S$，树上第 $i$ 条边连接编号为 $u_i$ 和 $v_i$ 的两个点，边权为 $w_i$。对于编号为 $i$ 的点而言，蒜头君定义 $s$ 值表示以编号为 $i$ 的节点为根节点的子树中节点的数量。

蒜头君定义树上的节点的深度为如下的值：根节点的深度为 $0$，如果节点 $x$ 的深度为 $d(x)$，则其子节点的深度为 $d(x)+1$。

若第 $i$ 条边连接的两个点中，深度较大的点为 $p_i$，则 $w_i$ 的值等于以 $p_i$ 为根的子树中的所有节点中，满足其 $s$ 值大于给定常数 $k$ 的节点数量。

定义一条路径的权值为路径上所有边的权值进行与运算后的值，记 $f(x,y)$ 为 $x$ 到 $y$ 的路径的权值。特别的，$f(x,x)=0$。

定义一个点 $x$ 的神秘值为 $\max_{i=1}^n\{f(x,i)\}$。

请你求出树上每一个点的神秘值。

输入格式

第一行两个整数 $n,S,k$ 表示树的节点数，根节点编号和给定常数。

下面 $n$ 行每行三个整数 $u_i,v_i$，表示 $u_i,v_i$ 之间存在一条边。保证这些边构成一棵树。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示 $i$ 点的神秘值。

数据范围

对于 $30\%$ 的数据，满足 $n\leq 300$。

对于 $50\%$ 的数据，满足 $n\leq 5\times 10^3$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^5,1\leq u_i,v_i\leq n$。

本题的输入量较大，请使用读入优化。

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

5 5 2 2 1 1 0 0 0 0 0