Reconstructing the Minimal Genetic Code

An original organism has a genetic code represented by a sequence of natural numbers $$K=(a_1, a_2,\dots,a_n)$$. A feature of the organism is defined as a consecutive pair \((l,r)\) in the genetic code, i.e. there exists an index $$i$$ such that \(l=a_i\) and \(r=a_{i+1}\). It is guaranteed that no feature is of the form \((p,p)\) (i.e. consecutive identical numbers never occur).

Given a set of features, the task is to construct the shortest possible genetic code (a sequence of natural numbers) that contains every given feature as a contiguous subsequence. In other words, for each provided pair \((u,v)\) there should exist an index \(i\) in the final sequence such that \(s_i=u\) and \(s_{i+1}=v\).

Note that if two features can be naturally linked because the second number of one equals the first number of the other, they can overlap in the constructed sequence (saving one number). Otherwise, the features must appear disjointly, and extra numbers are needed to join them.

Your program must compute the shortest such sequence and output it. The sequence should be output as a list of numbers separated by spaces.

Approach Hint: Think of each feature as a two‐character string. A natural overlap of length 1 is possible if the second element of one feature equals the first element of the next feature. You may solve the problem by trying all permutations of the features (using bitmask DP for instance) and selecting the ordering that minimizes the total number of extra numbers required.

inputFormat

The first line contains a positive integer \(m\) (the number of features). Each of the following \(m\) lines contains two natural numbers \(u\) and \(v\) (with \(u \neq v\)), representing a feature \((u,v)\).

outputFormat

Output a single line containing the shortest genetic code, represented as a sequence of natural numbers separated by spaces. The printed sequence must contain every given feature as a contiguous subsequence.

sample

3
1 2
2 3
3 1

1 2 3 1