#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
std::vector<int> a[1001];
bool visit[1001] = { false, };
 
void dfs(int s, int n) {
    visit[s] = true;
    printf("%d ", s);
 
    for (int i = 0; i < a[s].size(); i++) {
        if (!visit[a[s][i]]) dfs(a[s][i], n);
    }
}
 
void bfs(int s, int n) {
    std::queue<int> q;
 
    for (int i = 1; i <= n; i++)
        visit[i] = false;
    q.push(s);
    visit[s] = true;
 
    for (int i = 0; !q.empty(); i++) {
        int qf = q.front();
        for (int j = 0; j < a[qf].size(); j++) {
            if (!visit[a[qf][j]]) {
                q.push(a[qf][j]);
                visit[a[qf][j]] = true;
            }
        }
        printf("%d ", q.front());
        q.pop();
    }
}
 
int main()
{
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
 
    for (int i = 1; i <= n; i++)
        std::sort(a[i].begin(),a[i].end());
 
    dfs(v, n);
    printf("\n");
    bfs(v, n);
 
    return 0;
}

#include <iostream>
  
int a[1001],dp[1001];
  
int main()
{
        int n,i,j,max=0,maxi;
        //입력
        std::cin>>n;
        for(i=0;i<n;i++) std::cin>>a[i];
        //dp strat
        for(i=0;i<n;i++)
        {
                 for(j=0;j<i;j++)
                 {
                         if(a[j]<a[i] && dp[j]>=dp[i]) dp[i]=dp[j]+1;
                 }
                 if(dp[i]==0) dp[i]++;
                if(dp[i]>max) max=dp[i];
        }
        //출력
        std::cout<<max<<'\n';
        return 0;
}