NC53306. 水星上的服务器
描述
水星上有编号为1到N的N台服务器，这些服务器的通讯呈链式结构。具体来说，我们用N-1条信道（视为无向边）连接了这些服务器，第i条信道连接i号服务器和i+1号服务器。
假设j号服务器收到了地球发来的补丁。你需要尽快将补丁传输到其他服务器。
一台服务器收到补丁后，会立刻安装这个补丁（安装时间忽略不计），并且将补丁在这台服务器的缓冲区里保留
秒，之后将其删除。
由于太阳活动的影响，第i条通信信道只能在时段
（时刻
到时刻
）接通。某条通信信道接通后，如果信道一端的服务器A的缓冲区里有补丁，而另一端的服务器B没有安装这个补丁，A就会通过信道向B传输这个补丁。请注意，传输补丁的时间忽略不计。注意，你可以任选地球把补丁发给j号服务器的时刻。
对于每个j)
，假设j号服务器第一个收到补丁，试求：最早在什么时候把补丁发给j号服务器，才能保证所有服务器最后都能装上补丁，如果不可能，请输出-1。
假设j号服务器收到了地球发来的补丁。你需要尽快将补丁传输到其他服务器。
一台服务器收到补丁后，会立刻安装这个补丁（安装时间忽略不计），并且将补丁在这台服务器的缓冲区里保留
由于太阳活动的影响，第i条通信信道只能在时段
对于每个j
输入描述
第一行有一个整数n。
第二行有n个整数。
在接下来的n-1行中，每行两个整数
输出描述
输出n行，每行一个整数，表示：最早在什么时候把补丁发给j号服务器，才能保证所有服务器最后都能装上补丁。若不可能，请输出-1。
示例1
输入:
1 10
输出:
0
示例2
输入:
2 3 5 6 8
输出:
3 1
示例3
输入:
3 1 2 4 7 10 3 5
输出:
-1 5 5
说明:
如果1号服务器首先收到补丁，3号服务器就无法得到补丁，因为2号信道在1号信道开启前就关闭了。如果2号服务器在第5秒收到补丁，则3号服务器可以立即收到补丁，之后，等到第7秒时1号信道开启时，1号服务器就会收到补丁。
如果3号服务器在第5秒收到补丁，则2号服务器可以立即收到补丁，之后，等到第7秒时1号信道开启时，1号服务器就会收到补丁。
示例4
输入:
4 1 0 3 2 4 6 5 5 7 10
输出:
5 5 4 -1
说明:
若2号服务器首先收到补丁，由于2号服务器从不缓存，且2号信道只在第5秒开启，为了让3号服务器拿到补丁，你只能选择在第5秒把补丁发给2号服务器。若3号服务器首先收到补丁，不妨选择第4秒，3号服务器会将其缓存至第7秒，这样2号和4号服务器都能拿到补丁。