#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N=510;
int n,m,k;
bool st[N];
//int ss=1,tt=2;//求1-2的路径是否存在
//int s=1,t=2;// s起点，t终点
int ss=1,tt=6;
int pre[N];
int s=1,t=6;
vector<int> path;

struct Node
{
    int id;
    int w;//权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}

}*head[N];

void add(int a,int b)
{
    Node *p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
/*
void bfs(int u)//bfs求ss-tt的路径是否存在
{
    queue<int> q;
    q.push(u);
    st[u]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        if(t==tt)
        {
            printf("存在%d-%d的路径\n",ss,tt);
            return;
        }

        for(Node* p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!st[j])
            {
                st[j]=true;
                q.push(j);
            }
        }
    }
}

int main()//bfs求ss-tt的路径是否存在
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);

    }
    bfs(ss);
    return 0;
}

void dfs(int u)//dfs求s-t的路径是否存在
{
    st[u]=true;
    if(u==t)
    {
        printf("存在%d-%d的路径", s, t);
        return;
    }

    for(Node *p=head[u];p;p=p->next)
    {
        if(!st[p->id])
        dfs(p->id);
    }
}
int main()//dfs求s-t的路径是否存在
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    for(int i=1;i<=n;i++)
    {
        printf("%d: ",i);
        for(Node* p=head[i];p;p=p->next)
        printf("%d -> ",p->id);
        puts("NULL");
    }

    puts("-------------------");
    dfs(s);

    return 0;
}
*/
//如果是求具体路径呢?即1-6都经过了哪些点
/*
int main()//测试例子
{
6 6
1 2
1 3
1 4
2 3
3 4
2 6
}
*/
/*
void bfs(int u)//如果是求具体路径呢?即1-6都经过了哪些点
{
    queue<int> q;
    q.push(u);
    st[u]=true;
    pre[u]=-1; // 起点的前驱设为-1

    while(q.size())
    {
        int t=q.front();
        q.pop();

        if(t==tt)
        {
             printf("存在%d-%d的路径\n", ss, tt);

             //输出路径
             vector<int> path;
             for(int i=tt;i!=-1;i=pre[i])
             {
                 path.push_back(i);
             }
             reverse(path.begin(),path.end());

             printf("路径为：");
             for(int i=0;i<path.size();i++)
             {
                 if(i>0)printf("->");
                 printf("%d",path[i]);
             }
             printf("\n");
             return;
        }

        for(Node* p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!st[j])
            {
                st[j]=true;
                pre[j]=t;// 记录前驱节点
                q.push(j);
            }
        }
    }
    printf("不存在%d-%d的路径\n", ss, tt);
}

int main()//如果是求具体路径呢?即1-6都经过了哪些点
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs(ss);
    return 0;
}

bool dfs(int u)//DFS——退出递归时输出 对应 树的后序遍历（联想上节课树中找 m 到 n 的路径后续遍历的写法）
{
    st[u]=true;

    if(u==t)
    {
        cout<<u;
        return true;
    }

    for(Node* p=head[u];p;p=p->next)
    {
        if(!st[p->id])
        {
            if(dfs(p->id))
            {
                cout<<"<-"<<u;// 在回溯时输出当前节点
                return true;
            }
        }
    }
    return false;
}

int main()//DFS——退出递归时输出 对应 树的后序遍历（联想上节课树中找 m 到 n 的路径后续遍历的写法）
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    if(!dfs(s))
    {
        printf("不存在%d-%d的路径\n", s, t);
    }
    return 0;
}

void dfs(int s,int t)//输出从顶点s到顶点t的所有简单路径
{
    if(s==t)
    {
        for(auto x:path) printf("%d ",x);
        puts(" ");
        return;
    }

    for(auto p=head[s];p;p=p->next)
    {
        int j=p->id;
        if(!st[j])
        {
            st[j]=true;
            path.push_back(j);
            dfs(j,t);
            path.pop_back();
            st[j]=false;//返回后删除j,恢复未访问状态
        }
    }
}

int main()//输出从顶点s到顶点t的所有简单路径
{
    cin>>n>>m>>k;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    while(k--)
    {
        int s,t;
        cin>>s>>t;
        printf("\n%d -> %d 的简单路径：\n",s,t);
        path.push_back(s);
        st[s]=true;
        dfs(s,t);
        st[s]=false;
        path.pop_back();
    }
    return 0;

}
*/