using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4");
WillReturn.Add("0 2");
WillReturn.Add("0 1");
WillReturn.Add("2 2");
WillReturn.Add("0 1");
//2 4 3 1
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("0 1");
WillReturn.Add("0 1");
WillReturn.Add("0 1");
WillReturn.Add("0 1");
WillReturn.Add("0 1");
//1 2 3 4 5
}
else if (InputPattern == "Input3") {
WillReturn.Add("10");
WillReturn.Add("0 305186313");
WillReturn.Add("1 915059758");
WillReturn.Add("0 105282054");
WillReturn.Add("1 696409999");
WillReturn.Add("3 185928366");
WillReturn.Add("3 573289179");
WillReturn.Add("6 254538849");
WillReturn.Add("3 105282054");
WillReturn.Add("5 696409999");
WillReturn.Add("8 168629803");
//3 8 10 5 9 6 7 1 4 2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
class XYInfoDef
{
internal long ParentNode;
internal long CurrNode;
internal long EdgeCost;
internal long Level;
}
static List<XYInfoDef> mXYInfoList = new List<XYInfoDef>();
// XYInfo[ノード]なDict
static Dictionary<long, XYInfoDef> mXYInfoDict = new Dictionary<long, XYInfoDef>();
struct EdgeInfoDef
{
internal long ToNode;
internal long Cost;
}
static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict =
new Dictionary<long, List<EdgeInfoDef>>();
// 代表ノード[枝のハッシュ値]なDict
static Dictionary<string, long> mRootNodeDict1 = new Dictionary<string, long>();
// 代表ノード[ノード]なDict
static Dictionary<long, long> mRootNodeDict2 = new Dictionary<long, long>();
// ノードList[代表ノード]なDict
static Dictionary<long, List<long>> mNodeListDict = new Dictionary<long, List<long>>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
long CurrNodeNo = 1;
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
var WillAdd = new XYInfoDef();
WillAdd.CurrNode = CurrNodeNo;
WillAdd.ParentNode = wkArr[0];
WillAdd.EdgeCost = wkArr[1];
WillAdd.Level = long.MinValue;
mXYInfoList.Add(WillAdd);
mXYInfoDict[CurrNodeNo] = WillAdd;
CurrNodeNo++;
}
// 隣接リストを作成
foreach (XYInfoDef EachXYInfo in mXYInfoList) {
if (mEdgeInfoListDict.ContainsKey(EachXYInfo.ParentNode) == false) {
mEdgeInfoListDict[EachXYInfo.ParentNode] = new List<EdgeInfoDef>();
}
if (mEdgeInfoListDict.ContainsKey(EachXYInfo.CurrNode) == false) {
mEdgeInfoListDict[EachXYInfo.CurrNode] = new List<EdgeInfoDef>();
}
EdgeInfoDef WillAdd;
WillAdd.ToNode = EachXYInfo.CurrNode;
WillAdd.Cost = EachXYInfo.EdgeCost;
mEdgeInfoListDict[EachXYInfo.ParentNode].Add(WillAdd);
}
// DFSを行い、レベルを設定
ExecDFS();
// レベルの昇順にソート
mXYInfoList.Sort((A, B) => A.Level.CompareTo(B.Level));
// 代表ノード[ノード]なDict
mRootNodeDict2[0] = 0;
foreach (XYInfoDef EachXYInfo in mXYInfoList) {
long ParentNode = mRootNodeDict2[EachXYInfo.ParentNode];
long CurrNode = EachXYInfo.CurrNode;
string EdgeHash = GetEdgeHash(ParentNode, EachXYInfo.EdgeCost);
if (mRootNodeDict1.ContainsKey(EdgeHash) == false) {
mRootNodeDict1[EdgeHash] = CurrNode;
mRootNodeDict2[CurrNode] = CurrNode;
}
else {
long RootNode = mRootNodeDict1[EdgeHash];
mRootNodeDict2[CurrNode] = RootNode;
if (mEdgeInfoListDict.ContainsKey(CurrNode)) {
mEdgeInfoListDict[RootNode].AddRange(mEdgeInfoListDict[CurrNode]);
mEdgeInfoListDict[CurrNode].Clear();
}
}
}
// コストの昇順にソート
foreach (long EachKey in mEdgeInfoListDict.Keys.ToArray()) {
mEdgeInfoListDict[EachKey].Sort((A, B) => A.Cost.CompareTo(B.Cost));
}
foreach (var EachPair in mRootNodeDict2) {
if (mNodeListDict.ContainsKey(EachPair.Value) == false) {
mNodeListDict[EachPair.Value] = new List<long>();
}
mNodeListDict[EachPair.Value].Add(EachPair.Key);
}
// ノード番号の昇順にソート
foreach (long EachKey in mNodeListDict.Keys.ToArray()) {
mNodeListDict[EachKey].Sort((A, B) => A.CompareTo(B));
}
dfs(0);
Console.WriteLine(LongEnumJoin(" ", mAnswerList.Skip(1)));
}
static List<long> mAnswerList = new List<long>();
static HashSet<long> mVisitedSet = new HashSet<long>();
static void dfs(long pCurrNode)
{
pCurrNode = mRootNodeDict2[pCurrNode];
if (mVisitedSet.Add(pCurrNode) == false) return;
foreach (long EachNode in mNodeListDict[pCurrNode]) {
mAnswerList.Add(EachNode);
}
if (mEdgeInfoListDict.ContainsKey(pCurrNode)) {
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[pCurrNode]) {
dfs(EachEdgeInfo.ToNode);
}
}
}
// DFSを行い、レベルを設定
static void ExecDFS()
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrNode = 0;
WillPush.Level = 1;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
long CurrNode = Popped.CurrNode;
if (mXYInfoDict.ContainsKey(CurrNode)) {
mXYInfoDict[CurrNode].Level = Popped.Level;
}
if (mEdgeInfoListDict.ContainsKey(CurrNode)) {
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[CurrNode]) {
WillPush.CurrNode = EachEdgeInfo.ToNode;
WillPush.Level = Popped.Level + 1;
Stk.Push(WillPush);
}
}
}
}
struct JyoutaiDef
{
internal long CurrNode;
internal long Level;
}
// 親からの枝のハッシュを返す
static string GetEdgeHash(long pParentNode, long pEdgeCost)
{
return string.Format("{0},{1}", pParentNode, pEdgeCost);
}
// セパレータとLong型の列挙を引数として、結合したstringを返す
static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
}
}