IOI '06 P4 - The Valley of Mexico

#include <iostream>
#include <vector>

using namespace std;

#define bool char

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<bool>> connected(1+n, vector<bool>(1+n));
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        connected[u][v] = connected[v][u] = true;
    }

    auto previous = [&n](int i) {return i == 1 ? n : i-1;};
    auto next = [&n](int i) {return i == n ? 1 : i+1;};

    vector<vector<vector<bool>>> dp(1+n, vector<vector<bool>>(1+n, vector<bool>(2))); // l, r, last
    // last = 0 means last in the chain is left endpoint, 1 means last in the chain is right endpoint
    // dp[l][r][last] = 0 if impossible, 1 if possible

    for (int i = 1; i <= n; ++i) dp[i][i][0] = true;

    for (int width = 1; width < n; ++width) {
        for (int l = 1, r = width; l <= n; ++l, r = next(r)) {
            // try move to l-1
            int newL = previous(l);
            if (connected[l][newL] && dp[l][r][0] || connected[r][newL] && dp[l][r][1]) dp[newL][r][0] = true;

            // try move to r+1
            int newR = next(r);
            if (connected[l][newR] && dp[l][r][0] || connected[r][newR] && dp[l][r][1]) dp[l][newR][1] = true;
        }
    }

    bool found = false;
    for (int l = 1; l <= n; ++l) {
        int r = previous(l);
        if (dp[l][r][0] || dp[l][r][1]) {
            found = true;
            // reconstruct solution
            int last = (dp[l][r][0] ? 0 : 1);
            while (l != r) {
                if (last == 0) {
                    cout << l << '\n';
                    if (!connected[l][next(l)] || !dp[next(l)][r][0]) last = 1;
                    l = next(l);
                } else {
                    cout << r << '\n';
                    if (!connected[r][previous(r)] || !dp[l][previous(r)][1]) last = 0;
                    r = previous(r);
                }
            }
            cout << l << '\n';
            break;
        }
    }
    if (!found) cout << "-1\n";
    return 0;
}