Codeforces 29E AC (antigo)

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

#define rep(i,n) for (int i=0; i<n; i++)

#define TRACE(x)
#define PRINT(x...) TRACE(printf(x))
#define WATCH(x) TRACE(cout << #x << " = " << x << endl;)

#define fi first
#define se second
#define mp make_pair

int n,m;
int k;
queue< pair< pair<int, int>, int> > q;
vector<int> adj[510];
int dist[510][510][2];
pair<int, int> pre[510][510][2];
int bpath[510];
int apath[510];

void bfs() {
    q.push(mp(mp(0,n-1),0));
    dist[0][n-1][0]=0;

    while (!q.empty()) {
        int al=q.front().fi.fi;
        int bob=q.front().fi.se;
        int mv=q.front().se;
        q.pop();

        if (mv) rep(i,adj[al].size()) {
            int na=adj[al][i];
            if (bob==na) continue;
            if (dist[na][bob][0]!=-1) continue;

            dist[na][bob][0]=dist[al][bob][1]+1;
            pre[na][bob][0]=mp(al,bob);
            q.push(mp(mp(na,bob),0));
        }
        else rep(i,adj[bob].size()) {
            int nb=adj[bob][i];
            if (dist[al][nb][1]!=-1) continue;
            if (al==n-1 && nb==0) continue;

            dist[al][nb][1]=dist[al][bob][0]+1;
            pre[al][nb][1]=mp(al,bob);
            q.push(mp(mp(al,nb),1));
        }
    }
}

int main() {
    scanf("%d %d", &n,&m);
    rep(i,m) {
        int a,b;
        scanf("%d %d", &a,&b);
        adj[--a].push_back(--b);
        adj[b].push_back(a);
    }

    memset(dist,0xff, sizeof(dist));
    bfs();

    TRACE(
        rep(i,n) {
            rep(j,n) printf("(%d, %d) ", dist[i][j][0], dist[i][j][1]);
            printf("\n");
        }
    )

    if (dist[n-1][0][0]==-1) printf("-1\n");
    else {
        k=dist[n-1][0][0]/2;
        printf("%d\n", k);
        int a=n-1, b=0;
        int mv=0;

        for (int i=dist[n-1][0][0]; i>=0; i--) {
            apath[i/2]=a+1; bpath[(i+1)/2]=b+1;

            int tmp=pre[a][b][mv].fi;
            b=pre[a][b][mv].se;
            a=tmp; mv++; mv%=2;
        }

        rep(i,k+1) printf("%d ", apath[i]);
        printf("\n");
        rep(i,k+1) printf("%d ",bpath[i]);
        printf("\n");
    }

    return 0;
}