Lexicographically Smallest Level Ordering

Welcome to SAO (Strange and Abnormal Online)! In this VR MMORPG, you are given n levels with n-1 order constraints. Each constraint has the form \(u \to v\), indicating that level \(u\) must be completed before level \(v\) can be attempted.

It is guaranteed that if the directions are ignored, the underlying graph of constraints is connected; that is, no matter how you partition the levels into two non-empty sets, there will always be at least one constraint from one set to the other.

Your task is to output the lexicographically smallest valid ordering of all the levels. The lexicographically smallest ordering is defined by picking, at any step during a topological sort, the smallest available level number.

It is guaranteed that the given constraints form a Directed Acyclic Graph (in fact, a tree with directed edges), so a valid ordering exists.

inputFormat

The first line contains an integer \(n\) denoting the number of levels. The next \(n-1\) lines each contain two integers \(u\) and \(v\) (separated by a space) representing a constraint that level \(u\) must be completed before level \(v\) can be attempted.

outputFormat

Output a single line containing \(n\) integers separated by spaces — the lexicographically smallest valid ordering of levels satisfying the constraints.

sample

3
1 2
1 3

1 2 3