Harry's friend Charlie Weasley has partnered with an old-time breeder of dragons in Romania. When Harry visited Charlie over the summer, Charlie showed him breeding records stretching back centuries. It had started out with just one female dragon named Abraxia that had then reproduced to give many generations of dragons. The breeding record showed a family tree of dragons, starting with Abraxia and showing each descendant* (only females' descendants were shown), the year each was hatched from its egg and the year each died. Only already dead dragons were included. Charlie pointed out that a dragon matured early, and once hatched, could herself lay and hatch an egg in the very year it was born. Dragon eggs did not need a mother's care to hatch -- the breeders simply used the warmth of a blowtorch to keep the egg warm and hatch it, sometimes long after the mother dragon was dead.
Harry noticed that sometimes many generations of dragons were alive at the same time. He was curious to figure out, for each dragon when it was alive, what was the maximum generational difference (absolute value) between it and its coeval** descendants. Can you help him? Assume that if a dragon dies the year another is hatched, they were coeval.
*A descendant is a child, grandchild, great-grandchild etc.
**coeval: Alive at the same time.
Input (STDIN):
The first line contains the number of test cases T.
The first line of each test case starts with an integer N - the number of dragons.
It is followed by N lines. The ith line (0 indexed) contains 3 integers, p_i, hatchyear_i and deathyear_i. p_i is the parent of ith dragon and its interval is hatchyear_i to deathyear_i. The dragon with index 0 is Abraxia, and a mother's index is smaller than all its descendants'.
Output (STDOUT):
Output T lines.
Each line contains a space-separated list of N integers, the ith of them denoting the required answer for the ith dragon. If the ith dragon's life does not overlap with any descendant's, output 0 for that dragon.
Constraints:
1 <= T <= 3
1 <= N <= 70000
0 <= hatchyear <= deathyear <= 10^9
p_0 = -1
For all i > 0, 0 <= p_i < i
hatchyear of dragon >= hatchyear of its mother
Time Limit: 3s
Memory Limit: 64 MB
Sample Input:
2
5
-1 0 10
0 1 5
0 2 8
0 2 5
3 10 12
9
-1 0 10
0 1 1
0 2 2
1 2 3
1 3 4
2 2 3
2 2 4
6 10 11
6 20 30
Sample Output:
2 0 0 0 0
3 0 1 0 0 0 0 0 0
Harry's friend Charlie Weasley has partnered with an old-time breeder of dragons in Romania. When Harry visited Charlie over the summer, Charlie showed him breeding records stretching back centuries. It had started out with just one female dragon named Abraxia that had then reproduced to give many generations of dragons. The breeding record showed a family tree of dragons, starting with Abraxia and showing each descendant* (only females' descendants were shown), the year each was hatched from its egg and the year each died. Only already dead dragons were included. Charlie pointed out that a dragon matured early, and once hatched, could herself lay and hatch an egg in the very year it was born. Dragon eggs did not need a mother's care to hatch -- the breeders simply used the warmth of a blowtorch to keep the egg warm and hatch it, sometimes long after the mother dragon was dead.
Harry noticed that sometimes many generations of dragons were alive at the same time. He was curious to figure out, for each dragon when it was alive, what was the maximum generational difference (absolute value) between it and its coeval** descendants. Can you help him? Assume that if a dragon dies the year another is hatched, they were coeval.
*A descendant is a child, grandchild, great-grandchild etc.
**coeval: Alive at the same time.
Input (STDIN):
The first line contains the number of test cases T.
The first line of each test case starts with an integer N - the number of dragons.
It is followed by N lines. The ith line (0 indexed) contains 3 integers, p_i, hatchyear_i and deathyear_i. p_i is the parent of ith dragon and its interval is hatchyear_i to deathyear_i. The dragon with index 0 is Abraxia, and a mother's index is smaller than all its descendants'.
Output (STDOUT):
Output T lines.
Each line contains a space-separated list of N integers, the ith of them denoting the required answer for the ith dragon. If the ith dragon's life does not overlap with any descendant's, output 0 for that dragon.
Constraints:
1 <= T <= 3
1 <= N <= 70000
0 <= hatchyear <= deathyear <= 10^9
p_0 = -1
For all i > 0, 0 <= p_i < i
hatchyear of dragon >= hatchyear of its mother
Sample Input:
2
5
-1 0 10
0 1 5
0 2 8
0 2 5
3 10 12
9
-1 0 10
0 1 1
0 2 2
1 2 3
1 3 4
2 2 3
2 2 4
6 10 11
6 20 30
Sample Output:
2 0 0 0 0
3 0 1 0 0 0 0 0 0
