Tree Topological Sequences

We call a permutation \( \{p\} = \{p_1, p_2, \cdots, p_n\} \) of \(1 \dots n\) a topological sequence of a tree \(T\) (with \(n\) vertices labelled \(1\) to \(n\)) if and only if for every \(1 \le i i\) such that an edge exists between \(p_i\) and \(p_j\).

Given a tree \(T\), your task is to output as few topological sequences of \(T\) as possible, so that if and only if a tree \(T'\) has all these sequences as valid topological sequences then \(T' = T\). In other words, the set of sequences you provide must uniquely identify \(T\). It can be proved that a suitable (minimal) set of sequences always exists.

A valid topological sequence \(p_1,p_2,\dots,p_n\) must satisfy that for every \(1 \le i < n\), if we consider the unique edge chosen from vertex \(p_i\) (i.e. one of the edges incident to \(p_i\) connecting it with a vertex appearing later in the permutation), then exactly one such edge exists; and for the last element no such edge exists.

Input Format: The first line contains an integer \(n\) denoting the number of vertices. Then \(n-1\) lines follow, each containing two integers \(u\) and \(v\) indicating that there is an edge between vertices \(u\) and \(v\). It is guaranteed that these edges form a tree.

Output Format: Let \(k\) be the number of sequences in your answer. On the first line, output \(k\). Then output \(k\) lines, each containing a permutation of \(1,2,\dots,n\) (separated by spaces) that is a valid topological sequence of \(T\). The set of sequences you output must satisfy that if a tree \(T'\) has all these sequences as valid topological sequences then \(T' = T\). For this problem, it suffices to output the lexicographically smallest and the lexicographically largest valid topological sequences (when viewed as an array of numbers). (Note: For \(n=1\), only one sequence exists.)

Explanation:

A valid topological sequence yields an orientation of the tree \(T\) where every vertex except one (which appears last) selects exactly one adjacent vertex (which appears later in the permutation) and thereby acts as its "parent". One can show that if we choose a root and orient all edges on the unique paths toward the root then any linear extension in which every child comes before its parent is a valid topological sequence. In our solution, we generate two such sequences:

• The lexicographically smallest valid sequence is obtained by choosing the root as \(n\) (the largest vertex) and then performing a topological sort (of the induced DAG where each vertex \(v \neq n\) points to its parent on the unique path to \(n\)) using a min-heap.
• The lexicographically largest valid sequence is similarly obtained by choosing the root as \(1\) (the smallest vertex) and performing a topological sort with a max-heap.

Your submitted solutions in various programming languages should implement these ideas.

inputFormat

The input begins with an integer \(n\) (\(1 \le n \le 10^5\)), the number of vertices. The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), representing an edge between vertices \(u\) and \(v\). It is guaranteed that the given edges form a tree.

outputFormat

First, output an integer \(k\) on a single line denoting the number of topological sequences in your answer. For each of the next \(k\) lines, output a permutation of \(1,2,\dots,n\) (separated by spaces) which is a valid topological sequence of the given tree \(T\). For \(n > 1\), output two sequences: the lexicographically smallest valid sequence and the lexicographically largest valid sequence. For \(n = 1\), there is only one sequence.

sample

1

1
1