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("5 7");
WillReturn.Add("1 1 2");
WillReturn.Add("2 2");
WillReturn.Add("1 3 4");
WillReturn.Add("2 5");
WillReturn.Add("1 1 4");
WillReturn.Add("2 1");
WillReturn.Add("2 4");
//1 2
//5
//1 2 3 4
//1 2 3 4
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 2");
WillReturn.Add("2 1");
WillReturn.Add("2 1");
//1
//1
}
else if (InputPattern == "Input3") {
WillReturn.Add("3 3");
WillReturn.Add("1 1 2");
WillReturn.Add("2 1");
WillReturn.Add("1 1 2");
//1 2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int N = wkArr[0];
var InsUnionFind = new UnionFind();
for (int I = 1; I <= N; I++) {
InsUnionFind.MakeSet(I);
}
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int T = wkArr[0];
if (T == 1) {
int FromNode = wkArr[1];
int ToNode = wkArr[2];
InsUnionFind.Unite(FromNode, ToNode);
}
if (T == 2) {
int BaseNode = wkArr[1];
InsUnionFind.PrintNodeList(BaseNode);
}
}
}
}
// UnionFindクラス
internal class UnionFind
{
private class NodeInfoDef
{
internal long ParentNode;
internal long Rank;
internal List<long> NodeList;
}
private Dictionary<long, NodeInfoDef> mNodeInfoDict =
new Dictionary<long, NodeInfoDef>();
// 要素が1つである木を森に追加
internal void MakeSet(long pNode)
{
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
WillAdd.NodeList = new List<long>() { pNode };
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(long pX, long pY)
{
long XNode = FindSet(pX);
long YNode = FindSet(pY);
// 既に同じ木の場合
if (XNode == YNode) return;
long XRank = mNodeInfoDict[XNode].Rank;
long YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
mNodeInfoDict[XNode].NodeList.AddRange(mNodeInfoDict[YNode].NodeList);
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
mNodeInfoDict[YNode].NodeList.AddRange(mNodeInfoDict[XNode].NodeList);
if (XRank == YRank) {
mNodeInfoDict[YNode].Rank++;
}
}
}
// ノードを引数として、木の根を取得
internal long FindSet(long pTargetNode)
{
// 根までの経路上のノードのList
var PathNodeList = new List<long>();
long CurrNode = pTargetNode;
while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
PathNodeList.Add(CurrNode);
CurrNode = mNodeInfoDict[CurrNode].ParentNode;
}
// 経路圧縮 (親ポインタの付け替え)
foreach (long EachPathNode in PathNodeList) {
mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
}
return CurrNode;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
internal void PrintNodeList(long pBaseNode)
{
long RootNode = FindSet(pBaseNode);
mNodeInfoDict[RootNode].NodeList.Sort();
// セパレータとLong型の列挙を引数として、結合したstringを返す
Func<string, IEnumerable<long>, string> LongEnumJoin = (pSeparater, pEnum) =>
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
};
Console.WriteLine(LongEnumJoin(" ", mNodeInfoDict[RootNode].NodeList));
}
}