小红的基环树删边
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一棵基环树,她想知道,若删除第i条边,1号点到n号点的最短路是多少?
所谓基环树,指n个点、n条边组成的、不包含重边和自环的无向连通图。

输入描述:

第一行输入一个正整数n,代表基环树的点数。
接下来的n行,每行输入两个正整数u,v,代表节点u和节点v有一条边连接。
3\leq n \leq 10^5
1\leq u,v \leq n
保证给定的图为基环树。

输出描述:

输出n行,第i行输出删除第i条边的答案。如果删除后1号点和n号点不连通,请输出-1;否则输出一个正整数,代表删除后1号点和n号点的最短路长度。
示例1

输入

复制
3
1 2
2 3
1 3

输出

复制
1
1
2
示例2

输入

复制
4
1 2
2 3
2 4
3 4

输出

复制
-1
2
3
2