Ability Tree Tier Rollout

A game's ability tree is rooted at a single starting ability, and every other ability is unlocked directly beneath exactly one prerequisite ability (an ability may have any number of abilities unlocked beneath it). Players unlock the tree tier by tier: tier 0 is the root alone, tier 1 holds everything unlocked directly beneath the root, tier 2 holds everything unlocked directly beneath a tier-1 ability, and so on. Given the full prerequisite structure, report the ability ids that belong to each tier.

Input format

Line 1: an integer N — the number of abilities. Abilities are numbered 1..N, and ability 1 is always the root. Next N-1 lines: two integers u v — ability v is unlocked directly beneath ability u (u is v's immediate prerequisite). The edges may appear in any order, and every ability other than the root appears as v in exactly one edge.

Output format

Print one line per tier, starting with tier 0 (the root) and continuing down to the deepest tier that contains at least one ability. Each line lists the ids belonging to that tier, in strictly increasing numeric order, separated by single spaces.

Constraints

1 <= N <= 10^5 1 <= u, v <= N, u != v The edges, together with root 1, form a valid rooted tree.

7
1 2
1 3
1 4
2 5
2 6
4 7

1
2 3 4
5 6 7

1

1