從新竹搬到台北之後，喂喂感受到台北的食物非常好吃，而且每個捷運站附近都有一些好吃的食物。這天，喂喂肚子又餓了，他決定要出門到每一站捷運站附近吃東西恰好一次，不過因為部分捷運路線仍然在停駛當中，在僅存的捷運網路上的 $N$ 個捷運站中，任兩捷運站間存在恰好一條簡單路徑將其連接，換言之，捷運圖變成了一棵 $N$ 個點的樹，其中捷運站的編號為 $1$ ~ $N$，並且每一條邊都一樣長。

喂喂想要到每站捷運站附近吃東西恰好一次，不過因為喂喂腸胃炎，如果行程沒有效率那他可能在路上就會不小心拉完了，因此他需要你幫他決定一個吃美食行程，其為一個 $1$ ~ $N$ 的排列 $(p_1, p_2, ..., p_N)$，代表喂喂應依序去哪些捷運站吃美食，並且此排列應滿足兩個條件:

• 條件 1 : 對於行程中的第 $i$ 個捷運站點 $p_i$ ($2 \leq i \leq N$)，第 $i-1$ 個捷運站點 $p_{i-1}$ 應為當前拜訪過的捷運站點中與 $p_i$ 最近的站點之一，否則喂喂會覺得你在浪費他時間，嚴謹地說，若定義 $dis(u, v)$ 為兩捷運站點 $u, v$ 間在捷運圖上唯一簡單路徑上的邊數，則喂喂希望 $$dis(p_i, p_{i-1}) = \min(dis(p_i, p_1), dis(p_i, p_2), \ldots, dis(p_i, p_{i-1}))$$
• 條件 2 : 喂喂希望整個行程的總耗時越小越好，所以他希望行程在滿足條件 1 的情況下，最小化 $$dis(p_1, p_2) + dis(p_2, p_3) + \cdots + dis(p_{N-1}, p_N)$$

可以證明至少存在一組滿足條件 1 的捷運站點排列。