1 /*
 2      森林转换成二叉树
 3      思路：u的孩子节点为v1, v2, v3....（v1,v2,....互为兄弟节点） 
 4      那么将u的一个孩子节点（v1）连在u的左子树上，那么其他的孩子节点都连在v1的右子树上！ 
 5 */ 
 6 #include<iostream>
 7 #include<cstring>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 int g[15][15];
12 int par[15];//如果该节点有父亲节点说明该节点不是一个独立的点！ 
13 int vis[15];
14 
15 struct Tree{
16     int  d;
17     Tree *lchild, *rchild; 
18     Tree(){
19        lchild=rchild=NULL; 
20     }
21     
22     Tree(int x){
23        lchild=rchild=NULL; 
24        d=x;
25     }
26 };
27 int n, m;
28 
29 void buildT(Tree* &T, int u){
30     bool flag=false;
31     T=new Tree(u);
32     Tree *cur=T; 
33     vis[u]=1;
34     for(int v=1; v<=n; ++v)
35        if(g[u][v]){
36           if(!flag){
37              buildT(cur->lchild, v);
38              cur=cur->lchild;
39              flag=true;
40           }
41           else{
42              buildT(cur->rchild, v);
43              cur=cur->rchild;
44           }
45        }
46 }
47 
48 
49 void prePrint(Tree *T){
50    if(!T) return ;
51    cout<<T->d<<" ";
52    prePrint(T->lchild);
53    prePrint(T->rchild);
54 }
55 
56 
57 int main(){
58    Tree *T=NULL; 
59    while(cin>>n>>m){
60          memset(g, 0, sizeof(g));
61          memset(vis, 0, sizeof(vis));
62       while(m--){
63          int u, v;
64          cin>>u>>v;
65          g[u][v]=1;
66          par[v]=u;
67       }
68       bool flag=false;
69       Tree *cur;
70       for(int i=1; i<=n; ++i)
71           if(!vis[i]){ 
72              if(!flag){
73                 flag=true;
74                 buildT(T, i); 
75                 cur=T; 
76              }
77              else if(!par[i]){//也就是找入度为0的节点！ 
78                 buildT(cur->rchild, i);
79                 cur=cur->rchild;
80              }
81           }
82       prePrint(T);
83    }
84    return 0;
85 }
86  

//数组实现....森林转成二叉树以及二叉树还原成森林
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100 
using namespace std;

int mp[N][N];
int pp[N][N];
int n, m;
int ld[N], rd[N], par[N];

void printT(int u){
    if(u==0) return;
    printT(ld[u]);
    printT(rd[u]); 
    printf("%d ", u);
}

void rebuildMap(int u, int fa){
    if(u==0) return ;
    if(fa!=-1)  pp[fa][u]=1;
    rebuildMap(ld[u], u);
    rebuildMap(rd[u], fa);//u节点以及其兄弟节点的父亲节点都是u的父亲节点
} 

void buildT(int u){
    int v, cur;
    bool flag=false; 
    for(v=1; v<=n; ++v)
        if(mp[u][v]){
            if(!flag){
                ld[u]=v;
                cur=v;
                flag=true;
            }
            else{
                rd[cur]=v;//将u的兄弟节点都链接在右子树上
                cur=v;
            }
            buildT(v);
        } 
}

int main(){
    while(scanf("%d%d", &n, &m)!=EOF){
        memset(par, 0, sizeof(par));
        memset(pp, 0, sizeof(pp));
        memset(mp, 0, sizeof(mp));
        while(m--){
            int u, v;
            scanf("%d%d", &u, &v);
            mp[u][v]=1;
            par[v]=u;
        } 
        int root=-1, cur;
        for(int i=1; i<=n; ++i){
             if(!par[i]){
                 if(root!=-1) rd[cur]=i;
                 if(root==-1) root=i; 
                 buildT(i); 
                 cur=i;
             }
        }
        printf("打印树.....\n"); 
        printT(root);
        printf("\n");
        rebuildMap(root, -1);
        printf("\n\n还原树....\n"); 
        for(int i=1; i<=n; ++i)
              for(int j=1; j<=n; ++j)
                  if(pp[i][j])
                        printf("%d %d\n", i, j);
        printf("KO!\n"); 
    }
    return 0;
} 
/*
测试数据.....
11 8
2 1
2 3
2 4
5 6
6 9
5 7
5 8
11 10
*/