[HOJ] 295 - The Valley of Mexico

#include<stdio.h>
#include<algorithm>
#define f(x) ((x+n)%n)
using namespace std;
int map[1005][1005]={0},dp[1005][1005][2]={0};
int s[1005],n,m;
void dfs(int x,int y){
    int i,j,l,r,c=1,flag=y;
    l=r=x;
    s[0]=x;
    for(i=1;i<n;i++){
        if(flag==1){
            if(dp[f(l-1)][f(r+1)][0] && map[r][f(r+1)]){
                if(dp[f(r+1)][f(l-1)][1] && map[f(l-1)][r] && f(l-1)<f(r+1))
                    goto go;
                r=f(r+1);
                s[i]=r;
            }
            else{
                go:
                l=f(l-1);
                s[i]=l;
                flag=0;
            }
        }
        else{
            if(dp[f(r+1)][f(l-1)][1] && map[l][f(l-1)]){
                if(dp[f(l-1)][f(r+1)][0] && map[l][f(r+1)] && f(r+1)<f(l-1))
                    goto go2;
                l=f(l-1);
                s[i]=l;
            }
            else{
                go2:
                r=f(r+1);
                s[i]=r;
                flag=1;
            }
            /*if(dp[f(l-1)][f(r+1)][0] && map[l][f(r+1)]){
                r=f(r+1);
                s[i]=r;
                flag=1;
            }
            else{
                l=f(l-1);
                s[i]=l;
            }*/
        }
    }
    for(i=0;i<n;i++)
        printf("%d\n",s[i]+1);
    exit(0);
}
int main(){
    //freopen("mexico1.in","r",stdin);
    int i,j,x,y,r;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        map[x-1][y-1]=map[y-1][x-1]=1;
    }
    for(i=0;i<n;i++)
        dp[i][i][0]=dp[i][i][1]=1;
    for(j=1;j<n;j++){
        for(i=0;i<n;i++){
            dp[i][f(i-j)][0]=(dp[i][f(i-j+1)][0] && map[f(i-j+1)][f(i-j)]) ||
            (dp[f(i-j+1)][i][1] && map[i][f(i-j)]);
            dp[i][f(i+j)][1]=(dp[i][f(i+j-1)][1] && map[f(i+j-1)][f(i+j)]) ||
            (dp[f(i+j-1)][i][0] && map[i][f(i+j)]);
        }
    }
    /*for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            printf("%d ",dp[i][j][0]);
        puts("");
    }*/
    for(i=0;i<n;i++){
        if(dp[f(i-1)][i][0])
            dfs(i,0);
        if(dp[f(i+1)][i][1])
            dfs(i,1);
    }
    puts("-1");
}