강도의 여행

모노폴리스는 아름답고 부유한 나라다. 이 나라의 특징 중 하나는 도로망이다. 도시 $N$개가 길이가 같은 도로 $N-1$개로 이어져 있어서 어떤 두 도시든 서로 오갈 수 있다.

모노폴리스의 또 다른 특징은 각 도시에 은행이 하나씩 있고, 은행마다 보유한 돈이 서로 다르다는 것이다. 그래서 각 도시에 1부터 $N$까지 서로 다른 번호를 붙여 부의 순위를 나타낼 수 있다. 도시 1의 돈이 가장 적고, 도시 $N$의 돈이 가장 많다.

롭은 모노폴리스로 "출장"을 떠날 계획이다. 롭의 일은 강도질, 정확히는 은행털이다. 롭은 야심 있는 강도이며 정해진 방식을 따른다. 방금 턴 은행보다 돈이 많은 은행만 노린다. 도시 $i$에서 털고 나면 $i$보다 돈이 많은 도시 중 가장 가까운 곳으로 이동한다. 같은 거리에 그런 도시가 여러 곳이면 그중 돈이 가장 적은 도시를 고른다. $i$보다 부유한 도시가 없으면 롭은 같은 도시에 머물며 자신의 행동을 돌아본다.

롭은 이 방식을 엄격히 지키면서도 출장 계획에 도움을 청한다. 각 도시 $i$에 대해, 첫 번째 강도 짓을 도시 $i$에서 했을 때 다음으로 방문할 도시를 알고 싶어 한다.

첫 줄에 모노폴리스의 도시 수 $N$이 주어진다 ($1 \le N \le 10^5$). 각 도시는 부가 많아지는 순서대로 1부터 $N$까지의 서로 다른 정수로 구분된다.

이어지는 $N-1$개의 줄에는 정수 $U$와 $V$가 주어진다 ($1 \le U, V \le N$, $U \ne V$). 이는 도시 $U$와 $V$를 잇는 양방향 도로가 있다는 뜻이다. 주어진 도로로 모든 도시 쌍 사이에 경로가 존재함이 보장된다.

$N$개의 정수를 한 줄에 출력한다. $i$번째 정수는 첫 번째 강도 짓을 도시 $i$에서 했을 때 롭이 다음으로 방문할 도시다.