直接用栈模拟 dfs（不建边 dfs）需要注意第二次 dp 时机（应该在入栈时）。因为这个调了一晚上

另，附赠样例：

in

18
18 11
15 3
17 3
17 5
10 6
4 18
18 5
1 13
12 18
8 15
4 6
6 16
1 15
7 3
2 9
18 14
4 2
1
7
1 11 8 7 10 5 9 

out

3 1 1 2 3 6 2