Add files using upload-large-folder tool

1fd0050 verified 6 months ago

26.7 kB

#include <bits/stdc++.h>
using namespace std;

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx = 0, sz = 0;
    char buf[BUFSIZE];
    inline char gc() {
        if (idx >= sz) { sz = (int)fread(buf, 1, BUFSIZE, stdin); idx = 0; if (!sz) return 0; }
        return buf[idx++];
    }
    template<class T> bool readInt(T &out) {
        char c; T sign = 1; out = 0;
        do { c = gc(); if (!c) return false; } while (c <= ' ');
        if (c == '-') { sign = -1; c = gc(); }
        for (; c >= '0' && c <= '9'; c = gc()) out = out * 10 + (c - '0');
        out *= sign;
        return true;
    }
} fs;

static uint64_t rngState;
static inline uint64_t splitmix64() {
    uint64_t x = (rngState += 0x9e3779b97f4a7c15ULL);
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}
static inline int randInt(int n) { return (int)(splitmix64() % n); }

chrono::high_resolution_clock::time_point t0;
inline double elapsed() {
    return chrono::duration<double>(chrono::high_resolution_clock::now() - t0).count();
}

int n, m;
int *adjData, *radjData;
int *adjStart, *radjStart;
int *degOut, *degIn;
int *adjSorted;

inline bool hasEdge(int u, int v) {
    return binary_search(adjSorted + adjStart[u], adjSorted + adjStart[u] + degOut[u], v);
}

vector<int> bestPath;

void improvePath(vector<int>& path, double timeLim) {
    if (path.empty() || (int)path.size() == n) return;

    int *nxt = (int*)calloc(n + 1, sizeof(int));
    int *prv = (int*)calloc(n + 1, sizeof(int));
    char *used = (char*)calloc(n + 1, sizeof(char));

    for (int v : path) used[v] = 1;
    for (int i = 0; i + 1 < (int)path.size(); i++) {
        nxt[path[i]] = path[i + 1];
        prv[path[i + 1]] = path[i];
    }
    int head = path[0], tail = path.back();

    auto extendEnds = [&]() {
        while (true) {
            bool prog = false;
            while (true) {
                int best = 0;
                int s = adjStart[tail], l = degOut[tail];
                for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { best = adjData[s + j]; break; }
                if (!best) break;
                nxt[tail] = best; prv[best] = tail; used[best] = 1; tail = best; prog = true;
            }
            while (true) {
                int best = 0;
                int s = radjStart[head], l = degIn[head];
                for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { best = radjData[s + j]; break; }
                if (!best) break;
                prv[head] = best; nxt[best] = head; used[best] = 1; head = best; prog = true;
            }
            if (!prog) break;
        }
    };

    auto insertionPass = [&]() -> bool {
        bool changed = false;
        int u = head;
        while (u) {
            int w = nxt[u];
            if (!w) break;
            int s = adjStart[u], l = degOut[u];
            for (int j = 0; j < l; j++) {
                int v = adjData[s + j];
                if (!used[v] && hasEdge(v, w)) {
                    nxt[u] = v; prv[v] = u; nxt[v] = w; prv[w] = v;
                    used[v] = 1; changed = true; w = v;
                }
            }
            u = w;
        }
        return changed;
    };

    auto reverseInsertion = [&]() -> bool {
        bool changed = false;
        for (int v = 1; v <= n; v++) {
            if (used[v]) continue;
            bool ins = false;
            int s = adjStart[v], l = degOut[v];
            for (int j = 0; j < l && !ins; j++) {
                int w = adjData[s + j];
                if (!used[w]) continue;
                int u2 = prv[w];
                if (u2 && hasEdge(u2, v)) {
                    nxt[u2] = v; prv[v] = u2; nxt[v] = w; prv[w] = v;
                    used[v] = 1; changed = true; ins = true;
                }
            }
            if (ins) continue;
            int rs = radjStart[v], rl = degIn[v];
            for (int j = 0; j < rl && !ins; j++) {
                int u2 = radjData[rs + j];
                if (!used[u2]) continue;
                int w = nxt[u2];
                if (w && hasEdge(v, w)) {
                    nxt[u2] = v; prv[v] = u2; nxt[v] = w; prv[w] = v;
                    used[v] = 1; changed = true; ins = true;
                }
            }
            if (ins) continue;
            if (hasEdge(v, head)) {
                prv[head] = v; nxt[v] = head; head = v;
                used[v] = 1; changed = true;
            } else if (hasEdge(tail, v)) {
                nxt[tail] = v; prv[v] = tail; tail = v;
                used[v] = 1; changed = true;
            }
        }
        return changed;
    };

    extendEnds();
    for (int pass = 0; pass < 30; pass++) {
        bool ch = insertionPass();
        extendEnds();
        if (!ch) break;
    }
    for (int pass = 0; pass < 30 && elapsed() < timeLim; pass++) {
        bool ch = reverseInsertion();
        extendEnds();
        insertionPass();
        extendEnds();
        if (!ch) break;
    }

    // 2-vertex chain insertion
    if (n <= 1000 && elapsed() < timeLim) {
        for (int pass = 0; pass < 5 && elapsed() < timeLim; pass++) {
            bool changed = false;
            for (int v1 = 1; v1 <= n && elapsed() < timeLim; v1++) {
                if (used[v1]) continue;
                bool done = false;
                int s1 = adjStart[v1], l1 = degOut[v1];
                for (int j1 = 0; j1 < l1 && !done; j1++) {
                    int v2 = adjData[s1 + j1];
                    if (used[v2] || v2 == v1) continue;
                    int rs1 = radjStart[v1], rl1 = degIn[v1];
                    for (int j2 = 0; j2 < rl1 && !done; j2++) {
                        int u = radjData[rs1 + j2];
                        if (!used[u]) continue;
                        int w = nxt[u];
                        if (w && hasEdge(v2, w)) {
                            nxt[u] = v1; prv[v1] = u;
                            nxt[v1] = v2; prv[v2] = v1;
                            nxt[v2] = w; prv[w] = v2;
                            used[v1] = 1; used[v2] = 1;
                            changed = true; done = true;
                        }
                    }
                    // Also try: v1->v2 at head/tail
                    if (!done && hasEdge(v2, head)) {
                        int rs2 = radjStart[v1], rl2 = degIn[v1];
                        // v1 needs an in-edge from somewhere... actually just check if v1 can be at head
                        // Nothing feeds into v1 from the path, but v1 is the new head
                        // We need: v1 -> v2 -> head
                        nxt[v1] = v2; prv[v2] = v1; nxt[v2] = head; prv[head] = v2;
                        head = v1;
                        used[v1] = 1; used[v2] = 1;
                        changed = true; done = true;
                    }
                    if (!done && hasEdge(tail, v1)) {
                        nxt[tail] = v1; prv[v1] = tail; nxt[v1] = v2; prv[v2] = v1;
                        tail = v2;
                        used[v1] = 1; used[v2] = 1;
                        changed = true; done = true;
                    }
                }
            }
            extendEnds();
            insertionPass();
            reverseInsertion();
            extendEnds();
            if (!changed) break;
        }
    }

    // Reroute: for each edge u->w in path, try u->v->w where v is unused
    if (n <= 1000 && elapsed() < timeLim) {
        for (int pass = 0; pass < 5 && elapsed() < timeLim; pass++) {
            bool changed = false;
            int u = head;
            while (u && elapsed() < timeLim) {
                int w = nxt[u];
                if (!w) break;
                int s = adjStart[u], l = degOut[u];
                bool rerouted = false;
                for (int j = 0; j < l && !rerouted; j++) {
                    int v = adjData[s + j];
                    if (v == w || used[v]) continue;
                    if (hasEdge(v, w)) {
                        nxt[u] = v; prv[v] = u; nxt[v] = w; prv[w] = v;
                        used[v] = 1; changed = true; rerouted = true;
                    }
                }
                if (!rerouted) {
                    // Try u -> v1 -> v2 -> w
                    for (int j1 = 0; j1 < l && !rerouted; j1++) {
                        int v1 = adjData[s + j1];
                        if (v1 == w || used[v1]) continue;
                        int s2 = adjStart[v1], l2 = degOut[v1];
                        for (int j2 = 0; j2 < l2 && !rerouted; j2++) {
                            int v2 = adjData[s2 + j2];
                            if (v2 == w || v2 == v1 || used[v2]) continue;
                            if (hasEdge(v2, w)) {
                                nxt[u] = v1; prv[v1] = u;
                                nxt[v1] = v2; prv[v2] = v1;
                                nxt[v2] = w; prv[w] = v2;
                                used[v1] = 1; used[v2] = 1;
                                changed = true; rerouted = true;
                            }
                        }
                    }
                }
                u = nxt[u];
            }
            extendEnds();
            insertionPass();
            reverseInsertion();
            extendEnds();
            if (!changed) break;
        }
    }

    // Vertex swap: for each unused v, try to replace a path vertex b with v
    // such that b can be reinserted elsewhere
    if (n <= 500 && elapsed() < timeLim) {
        for (int pass = 0; pass < 3 && elapsed() < timeLim; pass++) {
            bool changed = false;
            for (int v = 1; v <= n && elapsed() < timeLim; v++) {
                if (used[v]) continue;
                // For each path node b, try replacing b with v
                // Requirements: prv[b]->v and v->nxt[b] (v replaces b)
                // Then b is free and can be reinserted
                for (int b = 1; b <= n; b++) {
                    if (!used[b]) continue;
                    int pb = prv[b], nb = nxt[b];
                    if (!pb && !nb) continue; // b is alone

                    bool canReplace = false;
                    if (pb && nb) canReplace = hasEdge(pb, v) && hasEdge(v, nb);
                    else if (!pb && nb) canReplace = hasEdge(v, nb); // b is head
                    else if (pb && !nb) canReplace = hasEdge(pb, v); // b is tail

                    if (!canReplace) continue;

                    // Remove b, insert v in b's place
                    if (pb) nxt[pb] = v; else head = v;
                    if (nb) prv[nb] = v; else tail = v;
                    prv[v] = pb; nxt[v] = nb;
                    used[v] = 1;
                    used[b] = 0; prv[b] = 0; nxt[b] = 0;

                    // Try to reinsert b
                    bool reins = false;
                    // Try between path nodes
                    for (int j = 0; j < degOut[b] && !reins; j++) {
                        int w = adjData[adjStart[b] + j];
                        if (!used[w]) continue;
                        int pu = prv[w];
                        if (pu && hasEdge(pu, b)) {
                            nxt[pu] = b; prv[b] = pu; nxt[b] = w; prv[w] = b;
                            used[b] = 1; reins = true;
                        }
                    }
                    if (!reins) {
                        for (int j = 0; j < degIn[b] && !reins; j++) {
                            int u2 = radjData[radjStart[b] + j];
                            if (!used[u2]) continue;
                            int w = nxt[u2];
                            if (w && hasEdge(b, w)) {
                                nxt[u2] = b; prv[b] = u2; nxt[b] = w; prv[w] = b;
                                used[b] = 1; reins = true;
                            }
                        }
                    }
                    if (!reins && hasEdge(b, head)) {
                        prv[head] = b; nxt[b] = head; head = b;
                        used[b] = 1; reins = true;
                    }
                    if (!reins && hasEdge(tail, b)) {
                        nxt[tail] = b; prv[b] = tail; tail = b;
                        used[b] = 1; reins = true;
                    }

                    if (reins) {
                        changed = true;
                        break; // done with v
                    } else {
                        // Undo: put b back, remove v
                        if (prv[v]) nxt[prv[v]] = b; else head = b;
                        if (nxt[v]) prv[nxt[v]] = b; else tail = b;
                        prv[b] = prv[v]; nxt[b] = nxt[v];
                        used[b] = 1;
                        used[v] = 0; prv[v] = 0; nxt[v] = 0;
                    }
                }
            }
            if (changed) {
                extendEnds();
                insertionPass();
                reverseInsertion();
                extendEnds();
            } else break;
        }
    }

    path.clear();
    for (int u = head; u; u = nxt[u]) {
        path.push_back(u);
        if ((int)path.size() > n) break;
    }

    free(nxt); free(prv); free(used);
}

vector<int> greedyPath(int start, int mode = 0) {
    // mode 0: first available, mode 1: Warnsdorff, mode 2: random
    char *used = (char*)calloc(n + 1, sizeof(char));
    deque<int> path;
    path.push_back(start);
    used[start] = 1;

    while (true) {
        bool prog = false;
        while (true) {
            int t = path.back();
            int best = 0;
            int s = adjStart[t], l = degOut[t];
            if (mode == 1) {
                int bestScore = INT_MAX;
                for (int j = 0; j < l; j++) {
                    int v = adjData[s + j];
                    if (!used[v]) {
                        int cnt = 0;
                        int vs = adjStart[v], vl = degOut[v];
                        for (int k = 0; k < vl; k++) if (!used[adjData[vs + k]]) cnt++;
                        if (cnt < bestScore) { bestScore = cnt; best = v; }
                    }
                }
            } else if (mode == 2) {
                // Random
                int cnt = 0;
                for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) cnt++;
                if (cnt > 0) {
                    int pick = randInt(cnt), k = 0;
                    for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { if (k == pick) { best = adjData[s + j]; break; } k++; }
                }
            } else {
                for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { best = adjData[s + j]; break; }
            }
            if (!best) break;
            path.push_back(best); used[best] = 1; prog = true;
        }
        while (true) {
            int h = path.front();
            int best = 0;
            int s = radjStart[h], l = degIn[h];
            if (mode == 1) {
                int bestScore = INT_MAX;
                for (int j = 0; j < l; j++) {
                    int u = radjData[s + j];
                    if (!used[u]) {
                        int cnt = 0;
                        int us = radjStart[u], ul = degIn[u];
                        for (int k = 0; k < ul; k++) if (!used[radjData[us + k]]) cnt++;
                        if (cnt < bestScore) { bestScore = cnt; best = u; }
                    }
                }
            } else if (mode == 2) {
                int cnt = 0;
                for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) cnt++;
                if (cnt > 0) {
                    int pick = randInt(cnt), k = 0;
                    for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { if (k == pick) { best = radjData[s + j]; break; } k++; }
                }
            } else {
                for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { best = radjData[s + j]; break; }
            }
            if (!best) break;
            path.push_front(best); used[best] = 1; prog = true;
        }
        if (!prog) break;
    }

    vector<int> result(path.begin(), path.end());
    free(used);
    return result;
}

bool dfsBacktrackFrom(int start, double timeLim, bool randomize = false) {
    char *used = (char*)calloc(n + 1, sizeof(char));
    int *pathArr = (int*)malloc(n * sizeof(int));
    int maxDeg = 0;
    for (int u = 1; u <= n; u++) if (degOut[u] > maxDeg) maxDeg = degOut[u];
    int *nbrBuf = (int*)malloc((long long)n * (maxDeg + 1) * sizeof(int));
    int *nbrCnt = (int*)malloc(n * sizeof(int));
    int *nbrIdx = (int*)malloc(n * sizeof(int));
    pair<int,int> *tmp = (pair<int,int>*)malloc((maxDeg + 1) * sizeof(pair<int,int>));
    bool found = false;

    int depth = 0;
    pathArr[0] = start;
    used[start] = 1;

    auto computeNbrs = [&](int d) {
        int v = pathArr[d];
        int s = adjStart[v], l = degOut[v];
        int tc = 0;
        for (int j = 0; j < l; j++) {
            int w = adjData[s + j];
            if (!used[w]) {
                int sc = 0;
                int ws = adjStart[w], wl = degOut[w];
                for (int k = 0; k < wl; k++) if (!used[adjData[ws + k]]) sc++;
                if (randomize) sc = sc * 1000 + (int)(splitmix64() % 1000);
                tmp[tc++] = {sc, w};
            }
        }
        sort(tmp, tmp + tc);
        long long base = (long long)d * (maxDeg + 1);
        for (int i = 0; i < tc; i++) nbrBuf[base + i] = tmp[i].second;
        nbrCnt[d] = tc;
        nbrIdx[d] = 0;
    };

    computeNbrs(0);
    long long checks = 0;

    while (depth >= 0) {
        if (++checks % 100000 == 0 && elapsed() > timeLim) break;

        if (depth == n - 1) {
            bestPath.assign(pathArr, pathArr + n);
            found = true;
            break;
        }

        if (depth + 1 > (int)bestPath.size()) {
            bestPath.assign(pathArr, pathArr + depth + 1);
        }

        bool went_deeper = false;
        long long base = (long long)depth * (maxDeg + 1);
        while (nbrIdx[depth] < nbrCnt[depth]) {
            int w = nbrBuf[base + nbrIdx[depth]];
            nbrIdx[depth]++;
            if (used[w]) continue;
            depth++;
            pathArr[depth] = w;
            used[w] = 1;
            computeNbrs(depth);
            went_deeper = true;
            break;
        }

        if (!went_deeper) {
            used[pathArr[depth]] = 0;
            depth--;
        }
    }

    free(used); free(pathArr); free(nbrBuf); free(nbrCnt); free(nbrIdx); free(tmp);
    return found;
}

vector<int> dpOnOrder(const vector<int>& order) {
    vector<int> pos(n + 1), dp(n + 1, 1), par(n + 1, 0);
    for (int i = 0; i < n; i++) pos[order[i]] = i;
    for (int i = 0; i < n; i++) {
        int v = order[i];
        int s = adjStart[v], l = degOut[v];
        for (int j = 0; j < l; j++) {
            int w = adjData[s + j];
            if (pos[w] > i && dp[v] + 1 > dp[w]) {
                dp[w] = dp[v] + 1;
                par[w] = v;
            }
        }
    }
    int bestV = 1, bestLen = dp[1];
    for (int v = 2; v <= n; v++) if (dp[v] > bestLen) { bestLen = dp[v]; bestV = v; }
    vector<int> path;
    int cur = bestV;
    while (cur) { path.push_back(cur); cur = par[cur]; }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    rngState = chrono::high_resolution_clock::now().time_since_epoch().count();
    t0 = chrono::high_resolution_clock::now();

    fs.readInt(n); fs.readInt(m);
    for (int i = 0; i < 10; i++) { int x; fs.readInt(x); }

    adjStart = (int*)calloc(n + 1, sizeof(int));
    radjStart = (int*)calloc(n + 1, sizeof(int));
    degOut = (int*)calloc(n + 1, sizeof(int));
    degIn = (int*)calloc(n + 1, sizeof(int));

    int *edgeU = (int*)malloc(m * sizeof(int));
    int *edgeV = (int*)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) {
        fs.readInt(edgeU[i]); fs.readInt(edgeV[i]);
        degOut[edgeU[i]]++;
        degIn[edgeV[i]]++;
    }

    for (int u = 1; u <= n; u++) {
        adjStart[u] = (u == 1) ? 0 : adjStart[u - 1] + degOut[u - 1];
        radjStart[u] = (u == 1) ? 0 : radjStart[u - 1] + degIn[u - 1];
    }

    adjData = (int*)malloc(m * sizeof(int));
    radjData = (int*)malloc(m * sizeof(int));
    {
        int *ac = (int*)malloc((n + 1) * sizeof(int));
        int *rc = (int*)malloc((n + 1) * sizeof(int));
        for (int u = 1; u <= n; u++) { ac[u] = adjStart[u]; rc[u] = radjStart[u]; }
        for (int i = 0; i < m; i++) {
            adjData[ac[edgeU[i]]++] = edgeV[i];
            radjData[rc[edgeV[i]]++] = edgeU[i];
        }
        free(ac); free(rc);
    }
    free(edgeU); free(edgeV);

    adjSorted = (int*)malloc(m * sizeof(int));
    memcpy(adjSorted, adjData, m * sizeof(int));
    for (int u = 1; u <= n; u++) {
        sort(adjSorted + adjStart[u], adjSorted + adjStart[u] + degOut[u]);
    }

    if (n <= 200) {
        // Small graph: DFS + many random greedy + improve

        // Phase 1: Deterministic DFS from best starts
        {
            vector<pair<int,int>> starts;
            for (int u = 1; u <= n; u++) starts.push_back({-(degOut[u] - degIn[u]), u});
            sort(starts.begin(), starts.end());

            bool found = false;
            for (int i = 0; i < (int)starts.size() && elapsed() < 0.8 && !found; i++) {
                double rem = 0.8 - elapsed();
                double t = max(rem / ((int)starts.size() - i), 0.01);
                found = dfsBacktrackFrom(starts[i].second, elapsed() + t, false);
            }

            // Phase 1b: Randomized DFS - many restarts
            if (!found) {
                while (elapsed() < 2.0 && (int)bestPath.size() < n) {
                    int sv = randInt(n) + 1;
                    found = dfsBacktrackFrom(sv, elapsed() + 0.1, true);
                    if (found) break;
                }
            }
        }

        // After DFS, try to improve immediately if we have a good path
        if ((int)bestPath.size() >= n * 3 / 4 && (int)bestPath.size() < n) {
            improvePath(bestPath, min(elapsed() + 1.0, 3.0));
        }

        if ((int)bestPath.size() < n) {
            // Phase 2: Warnsdorff greedy from all starts
            for (int s = 1; s <= n && elapsed() < 2.5; s++) {
                auto path = greedyPath(s, 1);
                if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
                if ((int)bestPath.size() == n) break;
            }
        }

        if ((int)bestPath.size() < n) {
            // Phase 3: Shuffled greedy
            while (elapsed() < 3.0 && (int)bestPath.size() < n) {
                for (int u = 1; u <= n; u++) {
                    int s = adjStart[u], l = degOut[u];
                    for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(adjData[s + i], adjData[s + j]); }
                    s = radjStart[u]; l = degIn[u];
                    for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(radjData[s + i], radjData[s + j]); }
                }
                int sv = randInt(n) + 1;
                auto path = greedyPath(sv, 2);
                if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
                if ((int)bestPath.size() == n) break;
                path = greedyPath(sv, 0);
                if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
            }
        }

        // Phase 4: Final improvement
        if ((int)bestPath.size() < n && !bestPath.empty())
            improvePath(bestPath, 3.8);

    } else {
        // Large graph: DP + greedy + improve
        {
            vector<int> order(n);
            for (int i = 0; i < n; i++) order[i] = i + 1;
            auto tryOrder = [&](vector<int>& ord) {
                auto path = dpOnOrder(ord);
                if ((int)path.size() > (int)bestPath.size()) bestPath = path;
            };

            sort(order.begin(), order.end(), [&](int x, int y) {
                int a = degOut[x] - degIn[x], b = degOut[y] - degIn[y];
                return a != b ? a > b : x < y;
            });
            tryOrder(order);
            sort(order.begin(), order.end(), [&](int x, int y) {
                return degOut[x] != degOut[y] ? degOut[x] > degOut[y] : x < y;
            });
            tryOrder(order);
            for (int iter = 0; elapsed() < 1.0 && (int)bestPath.size() < n; iter++) {
                for (size_t i = n - 1; i > 0; --i) { size_t j = splitmix64() % (i + 1); swap(order[i], order[j]); }
                tryOrder(order);
            }
        }

        if ((int)bestPath.size() < n && !bestPath.empty())
            improvePath(bestPath, 1.5);

        {
            vector<int> starts;
            int best = 1;
            for (int u = 2; u <= n; u++) if (degOut[u] - degIn[u] > degOut[best] - degIn[best]) best = u;
            starts.push_back(best);
            best = 1;
            for (int u = 2; u <= n; u++) if (degIn[u] < degIn[best]) best = u;
            starts.push_back(best);
            for (int i = 0; i < 50; i++) starts.push_back(randInt(n) + 1);

            for (int s : starts) {
                if (elapsed() > 2.5 || (int)bestPath.size() == n) break;
                auto path = greedyPath(s, 1);
                if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
                if ((int)bestPath.size() == n) break;
                path = greedyPath(s, 0);
                if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
            }
        }

        if ((int)bestPath.size() < n && !bestPath.empty())
            improvePath(bestPath, 3.0);

        if ((int)bestPath.size() < n) {
            while (elapsed() < 3.5 && (int)bestPath.size() < n) {
                for (int u = 1; u <= n; u++) {
                    int s = adjStart[u], l = degOut[u];
                    for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(adjData[s + i], adjData[s + j]); }
                    s = radjStart[u]; l = degIn[u];
                    for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(radjData[s + i], radjData[s + j]); }
                }
                auto path = greedyPath(randInt(n) + 1, 0);
                if ((int)path.size() > (int)bestPath.size()) {
                    bestPath = move(path);
                    if ((int)bestPath.size() < n) improvePath(bestPath, min(elapsed() + 0.3, 3.7));
                }
            }
        }
    }

    if (bestPath.empty()) bestPath.push_back(1);

    printf("%d\n", (int)bestPath.size());
    for (int i = 0; i < (int)bestPath.size(); i++) {
        if (i) putchar(' ');
        printf("%d", bestPath[i]);
    }
    putchar('\n');
    return 0;
}

	#include <bits/stdc++.h>
	using namespace std;

	struct FastScanner {
	static const int BUFSIZE = 1 << 20;
	int idx = 0, sz = 0;
	char buf[BUFSIZE];
	inline char gc() {
	if (idx >= sz) { sz = (int)fread(buf, 1, BUFSIZE, stdin); idx = 0; if (!sz) return 0; }
	return buf[idx++];
	}
	template<class T> bool readInt(T &out) {
	char c; T sign = 1; out = 0;
	do { c = gc(); if (!c) return false; } while (c <= ' ');
	if (c == '-') { sign = -1; c = gc(); }
	for (; c >= '0' && c <= '9'; c = gc()) out = out * 10 + (c - '0');
	out *= sign;
	return true;
	}
	} fs;

	static uint64_t rngState;
	static inline uint64_t splitmix64() {
	uint64_t x = (rngState += 0x9e3779b97f4a7c15ULL);
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
	}
	static inline int randInt(int n) { return (int)(splitmix64() % n); }

	chrono::high_resolution_clock::time_point t0;
	inline double elapsed() {
	return chrono::duration<double>(chrono::high_resolution_clock::now() - t0).count();
	}

	int n, m;
	int adjData, radjData;
	int adjStart, radjStart;
	int degOut, degIn;
	int *adjSorted;

	inline bool hasEdge(int u, int v) {
	return binary_search(adjSorted + adjStart[u], adjSorted + adjStart[u] + degOut[u], v);
	}

	vector<int> bestPath;

	void improvePath(vector<int>& path, double timeLim) {
	if (path.empty() \|\| (int)path.size() == n) return;

	int nxt = (int)calloc(n + 1, sizeof(int));
	int prv = (int)calloc(n + 1, sizeof(int));
	char used = (char)calloc(n + 1, sizeof(char));

	for (int v : path) used[v] = 1;
	for (int i = 0; i + 1 < (int)path.size(); i++) {
	nxt[path[i]] = path[i + 1];
	prv[path[i + 1]] = path[i];
	}
	int head = path[0], tail = path.back();

	auto extendEnds = [&]() {
	while (true) {
	bool prog = false;
	while (true) {
	int best = 0;
	int s = adjStart[tail], l = degOut[tail];
	for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { best = adjData[s + j]; break; }
	if (!best) break;
	nxt[tail] = best; prv[best] = tail; used[best] = 1; tail = best; prog = true;
	}
	while (true) {
	int best = 0;
	int s = radjStart[head], l = degIn[head];
	for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { best = radjData[s + j]; break; }
	if (!best) break;
	prv[head] = best; nxt[best] = head; used[best] = 1; head = best; prog = true;
	}
	if (!prog) break;
	}
	};

	auto insertionPass = [&]() -> bool {
	bool changed = false;
	int u = head;
	while (u) {
	int w = nxt[u];
	if (!w) break;
	int s = adjStart[u], l = degOut[u];
	for (int j = 0; j < l; j++) {
	int v = adjData[s + j];
	if (!used[v] && hasEdge(v, w)) {
	nxt[u] = v; prv[v] = u; nxt[v] = w; prv[w] = v;
	used[v] = 1; changed = true; w = v;
	}
	}
	u = w;
	}
	return changed;
	};

	auto reverseInsertion = [&]() -> bool {
	bool changed = false;
	for (int v = 1; v <= n; v++) {
	if (used[v]) continue;
	bool ins = false;
	int s = adjStart[v], l = degOut[v];
	for (int j = 0; j < l && !ins; j++) {
	int w = adjData[s + j];
	if (!used[w]) continue;
	int u2 = prv[w];
	if (u2 && hasEdge(u2, v)) {
	nxt[u2] = v; prv[v] = u2; nxt[v] = w; prv[w] = v;
	used[v] = 1; changed = true; ins = true;
	}
	}
	if (ins) continue;
	int rs = radjStart[v], rl = degIn[v];
	for (int j = 0; j < rl && !ins; j++) {
	int u2 = radjData[rs + j];
	if (!used[u2]) continue;
	int w = nxt[u2];
	if (w && hasEdge(v, w)) {
	nxt[u2] = v; prv[v] = u2; nxt[v] = w; prv[w] = v;
	used[v] = 1; changed = true; ins = true;
	}
	}
	if (ins) continue;
	if (hasEdge(v, head)) {
	prv[head] = v; nxt[v] = head; head = v;
	used[v] = 1; changed = true;
	} else if (hasEdge(tail, v)) {
	nxt[tail] = v; prv[v] = tail; tail = v;
	used[v] = 1; changed = true;
	}
	}
	return changed;
	};

	extendEnds();
	for (int pass = 0; pass < 30; pass++) {
	bool ch = insertionPass();
	extendEnds();
	if (!ch) break;
	}
	for (int pass = 0; pass < 30 && elapsed() < timeLim; pass++) {
	bool ch = reverseInsertion();
	extendEnds();
	insertionPass();
	extendEnds();
	if (!ch) break;
	}

	// 2-vertex chain insertion
	if (n <= 1000 && elapsed() < timeLim) {
	for (int pass = 0; pass < 5 && elapsed() < timeLim; pass++) {
	bool changed = false;
	for (int v1 = 1; v1 <= n && elapsed() < timeLim; v1++) {
	if (used[v1]) continue;
	bool done = false;
	int s1 = adjStart[v1], l1 = degOut[v1];
	for (int j1 = 0; j1 < l1 && !done; j1++) {
	int v2 = adjData[s1 + j1];
	if (used[v2] \|\| v2 == v1) continue;
	int rs1 = radjStart[v1], rl1 = degIn[v1];
	for (int j2 = 0; j2 < rl1 && !done; j2++) {
	int u = radjData[rs1 + j2];
	if (!used[u]) continue;
	int w = nxt[u];
	if (w && hasEdge(v2, w)) {
	nxt[u] = v1; prv[v1] = u;
	nxt[v1] = v2; prv[v2] = v1;
	nxt[v2] = w; prv[w] = v2;
	used[v1] = 1; used[v2] = 1;
	changed = true; done = true;
	}
	}
	// Also try: v1->v2 at head/tail
	if (!done && hasEdge(v2, head)) {
	int rs2 = radjStart[v1], rl2 = degIn[v1];
	// v1 needs an in-edge from somewhere... actually just check if v1 can be at head
	// Nothing feeds into v1 from the path, but v1 is the new head
	// We need: v1 -> v2 -> head
	nxt[v1] = v2; prv[v2] = v1; nxt[v2] = head; prv[head] = v2;
	head = v1;
	used[v1] = 1; used[v2] = 1;
	changed = true; done = true;
	}
	if (!done && hasEdge(tail, v1)) {
	nxt[tail] = v1; prv[v1] = tail; nxt[v1] = v2; prv[v2] = v1;
	tail = v2;
	used[v1] = 1; used[v2] = 1;
	changed = true; done = true;
	}
	}
	}
	extendEnds();
	insertionPass();
	reverseInsertion();
	extendEnds();
	if (!changed) break;
	}
	}

	// Reroute: for each edge u->w in path, try u->v->w where v is unused
	if (n <= 1000 && elapsed() < timeLim) {
	for (int pass = 0; pass < 5 && elapsed() < timeLim; pass++) {
	bool changed = false;
	int u = head;
	while (u && elapsed() < timeLim) {
	int w = nxt[u];
	if (!w) break;
	int s = adjStart[u], l = degOut[u];
	bool rerouted = false;
	for (int j = 0; j < l && !rerouted; j++) {
	int v = adjData[s + j];
	if (v == w \|\| used[v]) continue;
	if (hasEdge(v, w)) {
	nxt[u] = v; prv[v] = u; nxt[v] = w; prv[w] = v;
	used[v] = 1; changed = true; rerouted = true;
	}
	}
	if (!rerouted) {
	// Try u -> v1 -> v2 -> w
	for (int j1 = 0; j1 < l && !rerouted; j1++) {
	int v1 = adjData[s + j1];
	if (v1 == w \|\| used[v1]) continue;
	int s2 = adjStart[v1], l2 = degOut[v1];
	for (int j2 = 0; j2 < l2 && !rerouted; j2++) {
	int v2 = adjData[s2 + j2];
	if (v2 == w \|\| v2 == v1 \|\| used[v2]) continue;
	if (hasEdge(v2, w)) {
	nxt[u] = v1; prv[v1] = u;
	nxt[v1] = v2; prv[v2] = v1;
	nxt[v2] = w; prv[w] = v2;
	used[v1] = 1; used[v2] = 1;
	changed = true; rerouted = true;
	}
	}
	}
	}
	u = nxt[u];
	}
	extendEnds();
	insertionPass();
	reverseInsertion();
	extendEnds();
	if (!changed) break;
	}
	}

	// Vertex swap: for each unused v, try to replace a path vertex b with v
	// such that b can be reinserted elsewhere
	if (n <= 500 && elapsed() < timeLim) {
	for (int pass = 0; pass < 3 && elapsed() < timeLim; pass++) {
	bool changed = false;
	for (int v = 1; v <= n && elapsed() < timeLim; v++) {
	if (used[v]) continue;
	// For each path node b, try replacing b with v
	// Requirements: prv[b]->v and v->nxt[b] (v replaces b)
	// Then b is free and can be reinserted
	for (int b = 1; b <= n; b++) {
	if (!used[b]) continue;
	int pb = prv[b], nb = nxt[b];
	if (!pb && !nb) continue; // b is alone

	bool canReplace = false;
	if (pb && nb) canReplace = hasEdge(pb, v) && hasEdge(v, nb);
	else if (!pb && nb) canReplace = hasEdge(v, nb); // b is head
	else if (pb && !nb) canReplace = hasEdge(pb, v); // b is tail

	if (!canReplace) continue;

	// Remove b, insert v in b's place
	if (pb) nxt[pb] = v; else head = v;
	if (nb) prv[nb] = v; else tail = v;
	prv[v] = pb; nxt[v] = nb;
	used[v] = 1;
	used[b] = 0; prv[b] = 0; nxt[b] = 0;

	// Try to reinsert b
	bool reins = false;
	// Try between path nodes
	for (int j = 0; j < degOut[b] && !reins; j++) {
	int w = adjData[adjStart[b] + j];
	if (!used[w]) continue;
	int pu = prv[w];
	if (pu && hasEdge(pu, b)) {
	nxt[pu] = b; prv[b] = pu; nxt[b] = w; prv[w] = b;
	used[b] = 1; reins = true;
	}
	}
	if (!reins) {
	for (int j = 0; j < degIn[b] && !reins; j++) {
	int u2 = radjData[radjStart[b] + j];
	if (!used[u2]) continue;
	int w = nxt[u2];
	if (w && hasEdge(b, w)) {
	nxt[u2] = b; prv[b] = u2; nxt[b] = w; prv[w] = b;
	used[b] = 1; reins = true;
	}
	}
	}
	if (!reins && hasEdge(b, head)) {
	prv[head] = b; nxt[b] = head; head = b;
	used[b] = 1; reins = true;
	}
	if (!reins && hasEdge(tail, b)) {
	nxt[tail] = b; prv[b] = tail; tail = b;
	used[b] = 1; reins = true;
	}

	if (reins) {
	changed = true;
	break; // done with v
	} else {
	// Undo: put b back, remove v
	if (prv[v]) nxt[prv[v]] = b; else head = b;
	if (nxt[v]) prv[nxt[v]] = b; else tail = b;
	prv[b] = prv[v]; nxt[b] = nxt[v];
	used[b] = 1;
	used[v] = 0; prv[v] = 0; nxt[v] = 0;
	}
	}
	}
	if (changed) {
	extendEnds();
	insertionPass();
	reverseInsertion();
	extendEnds();
	} else break;
	}
	}

	path.clear();
	for (int u = head; u; u = nxt[u]) {
	path.push_back(u);
	if ((int)path.size() > n) break;
	}

	free(nxt); free(prv); free(used);
	}

	vector<int> greedyPath(int start, int mode = 0) {
	// mode 0: first available, mode 1: Warnsdorff, mode 2: random
	char used = (char)calloc(n + 1, sizeof(char));
	deque<int> path;
	path.push_back(start);
	used[start] = 1;

	while (true) {
	bool prog = false;
	while (true) {
	int t = path.back();
	int best = 0;
	int s = adjStart[t], l = degOut[t];
	if (mode == 1) {
	int bestScore = INT_MAX;
	for (int j = 0; j < l; j++) {
	int v = adjData[s + j];
	if (!used[v]) {
	int cnt = 0;
	int vs = adjStart[v], vl = degOut[v];
	for (int k = 0; k < vl; k++) if (!used[adjData[vs + k]]) cnt++;
	if (cnt < bestScore) { bestScore = cnt; best = v; }
	}
	}
	} else if (mode == 2) {
	// Random
	int cnt = 0;
	for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) cnt++;
	if (cnt > 0) {
	int pick = randInt(cnt), k = 0;
	for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { if (k == pick) { best = adjData[s + j]; break; } k++; }
	}
	} else {
	for (int j = 0; j < l; j++) if (!used[adjData[s + j]]) { best = adjData[s + j]; break; }
	}
	if (!best) break;
	path.push_back(best); used[best] = 1; prog = true;
	}
	while (true) {
	int h = path.front();
	int best = 0;
	int s = radjStart[h], l = degIn[h];
	if (mode == 1) {
	int bestScore = INT_MAX;
	for (int j = 0; j < l; j++) {
	int u = radjData[s + j];
	if (!used[u]) {
	int cnt = 0;
	int us = radjStart[u], ul = degIn[u];
	for (int k = 0; k < ul; k++) if (!used[radjData[us + k]]) cnt++;
	if (cnt < bestScore) { bestScore = cnt; best = u; }
	}
	}
	} else if (mode == 2) {
	int cnt = 0;
	for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) cnt++;
	if (cnt > 0) {
	int pick = randInt(cnt), k = 0;
	for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { if (k == pick) { best = radjData[s + j]; break; } k++; }
	}
	} else {
	for (int j = 0; j < l; j++) if (!used[radjData[s + j]]) { best = radjData[s + j]; break; }
	}
	if (!best) break;
	path.push_front(best); used[best] = 1; prog = true;
	}
	if (!prog) break;
	}

	vector<int> result(path.begin(), path.end());
	free(used);
	return result;
	}

	bool dfsBacktrackFrom(int start, double timeLim, bool randomize = false) {
	char used = (char)calloc(n + 1, sizeof(char));
	int pathArr = (int)malloc(n * sizeof(int));
	int maxDeg = 0;
	for (int u = 1; u <= n; u++) if (degOut[u] > maxDeg) maxDeg = degOut[u];
	int nbrBuf = (int)malloc((long long)n * (maxDeg + 1) * sizeof(int));
	int nbrCnt = (int)malloc(n * sizeof(int));
	int nbrIdx = (int)malloc(n * sizeof(int));
	pair<int,int> tmp = (pair<int,int>)malloc((maxDeg + 1) * sizeof(pair<int,int>));
	bool found = false;

	int depth = 0;
	pathArr[0] = start;
	used[start] = 1;

	auto computeNbrs = [&](int d) {
	int v = pathArr[d];
	int s = adjStart[v], l = degOut[v];
	int tc = 0;
	for (int j = 0; j < l; j++) {
	int w = adjData[s + j];
	if (!used[w]) {
	int sc = 0;
	int ws = adjStart[w], wl = degOut[w];
	for (int k = 0; k < wl; k++) if (!used[adjData[ws + k]]) sc++;
	if (randomize) sc = sc * 1000 + (int)(splitmix64() % 1000);
	tmp[tc++] = {sc, w};
	}
	}
	sort(tmp, tmp + tc);
	long long base = (long long)d * (maxDeg + 1);
	for (int i = 0; i < tc; i++) nbrBuf[base + i] = tmp[i].second;
	nbrCnt[d] = tc;
	nbrIdx[d] = 0;
	};

	computeNbrs(0);
	long long checks = 0;

	while (depth >= 0) {
	if (++checks % 100000 == 0 && elapsed() > timeLim) break;

	if (depth == n - 1) {
	bestPath.assign(pathArr, pathArr + n);
	found = true;
	break;
	}

	if (depth + 1 > (int)bestPath.size()) {
	bestPath.assign(pathArr, pathArr + depth + 1);
	}

	bool went_deeper = false;
	long long base = (long long)depth * (maxDeg + 1);
	while (nbrIdx[depth] < nbrCnt[depth]) {
	int w = nbrBuf[base + nbrIdx[depth]];
	nbrIdx[depth]++;
	if (used[w]) continue;
	depth++;
	pathArr[depth] = w;
	used[w] = 1;
	computeNbrs(depth);
	went_deeper = true;
	break;
	}

	if (!went_deeper) {
	used[pathArr[depth]] = 0;
	depth--;
	}
	}

	free(used); free(pathArr); free(nbrBuf); free(nbrCnt); free(nbrIdx); free(tmp);
	return found;
	}

	vector<int> dpOnOrder(const vector<int>& order) {
	vector<int> pos(n + 1), dp(n + 1, 1), par(n + 1, 0);
	for (int i = 0; i < n; i++) pos[order[i]] = i;
	for (int i = 0; i < n; i++) {
	int v = order[i];
	int s = adjStart[v], l = degOut[v];
	for (int j = 0; j < l; j++) {
	int w = adjData[s + j];
	if (pos[w] > i && dp[v] + 1 > dp[w]) {
	dp[w] = dp[v] + 1;
	par[w] = v;
	}
	}
	}
	int bestV = 1, bestLen = dp[1];
	for (int v = 2; v <= n; v++) if (dp[v] > bestLen) { bestLen = dp[v]; bestV = v; }
	vector<int> path;
	int cur = bestV;
	while (cur) { path.push_back(cur); cur = par[cur]; }
	reverse(path.begin(), path.end());
	return path;
	}

	int main() {
	rngState = chrono::high_resolution_clock::now().time_since_epoch().count();
	t0 = chrono::high_resolution_clock::now();

	fs.readInt(n); fs.readInt(m);
	for (int i = 0; i < 10; i++) { int x; fs.readInt(x); }

	adjStart = (int*)calloc(n + 1, sizeof(int));
	radjStart = (int*)calloc(n + 1, sizeof(int));
	degOut = (int*)calloc(n + 1, sizeof(int));
	degIn = (int*)calloc(n + 1, sizeof(int));

	int edgeU = (int)malloc(m * sizeof(int));
	int edgeV = (int)malloc(m * sizeof(int));
	for (int i = 0; i < m; i++) {
	fs.readInt(edgeU[i]); fs.readInt(edgeV[i]);
	degOut[edgeU[i]]++;
	degIn[edgeV[i]]++;
	}

	for (int u = 1; u <= n; u++) {
	adjStart[u] = (u == 1) ? 0 : adjStart[u - 1] + degOut[u - 1];
	radjStart[u] = (u == 1) ? 0 : radjStart[u - 1] + degIn[u - 1];
	}

	adjData = (int)malloc(m sizeof(int));
	radjData = (int)malloc(m sizeof(int));
	{
	int ac = (int)malloc((n + 1) * sizeof(int));
	int rc = (int)malloc((n + 1) * sizeof(int));
	for (int u = 1; u <= n; u++) { ac[u] = adjStart[u]; rc[u] = radjStart[u]; }
	for (int i = 0; i < m; i++) {
	adjData[ac[edgeU[i]]++] = edgeV[i];
	radjData[rc[edgeV[i]]++] = edgeU[i];
	}
	free(ac); free(rc);
	}
	free(edgeU); free(edgeV);

	adjSorted = (int)malloc(m sizeof(int));
	memcpy(adjSorted, adjData, m * sizeof(int));
	for (int u = 1; u <= n; u++) {
	sort(adjSorted + adjStart[u], adjSorted + adjStart[u] + degOut[u]);
	}

	if (n <= 200) {
	// Small graph: DFS + many random greedy + improve

	// Phase 1: Deterministic DFS from best starts
	{
	vector<pair<int,int>> starts;
	for (int u = 1; u <= n; u++) starts.push_back({-(degOut[u] - degIn[u]), u});
	sort(starts.begin(), starts.end());

	bool found = false;
	for (int i = 0; i < (int)starts.size() && elapsed() < 0.8 && !found; i++) {
	double rem = 0.8 - elapsed();
	double t = max(rem / ((int)starts.size() - i), 0.01);
	found = dfsBacktrackFrom(starts[i].second, elapsed() + t, false);
	}

	// Phase 1b: Randomized DFS - many restarts
	if (!found) {
	while (elapsed() < 2.0 && (int)bestPath.size() < n) {
	int sv = randInt(n) + 1;
	found = dfsBacktrackFrom(sv, elapsed() + 0.1, true);
	if (found) break;
	}
	}
	}

	// After DFS, try to improve immediately if we have a good path
	if ((int)bestPath.size() >= n * 3 / 4 && (int)bestPath.size() < n) {
	improvePath(bestPath, min(elapsed() + 1.0, 3.0));
	}

	if ((int)bestPath.size() < n) {
	// Phase 2: Warnsdorff greedy from all starts
	for (int s = 1; s <= n && elapsed() < 2.5; s++) {
	auto path = greedyPath(s, 1);
	if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
	if ((int)bestPath.size() == n) break;
	}
	}

	if ((int)bestPath.size() < n) {
	// Phase 3: Shuffled greedy
	while (elapsed() < 3.0 && (int)bestPath.size() < n) {
	for (int u = 1; u <= n; u++) {
	int s = adjStart[u], l = degOut[u];
	for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(adjData[s + i], adjData[s + j]); }
	s = radjStart[u]; l = degIn[u];
	for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(radjData[s + i], radjData[s + j]); }
	}
	int sv = randInt(n) + 1;
	auto path = greedyPath(sv, 2);
	if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
	if ((int)bestPath.size() == n) break;
	path = greedyPath(sv, 0);
	if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
	}
	}

	// Phase 4: Final improvement
	if ((int)bestPath.size() < n && !bestPath.empty())
	improvePath(bestPath, 3.8);

	} else {
	// Large graph: DP + greedy + improve
	{
	vector<int> order(n);
	for (int i = 0; i < n; i++) order[i] = i + 1;
	auto tryOrder = [&](vector<int>& ord) {
	auto path = dpOnOrder(ord);
	if ((int)path.size() > (int)bestPath.size()) bestPath = path;
	};

	sort(order.begin(), order.end(), [&](int x, int y) {
	int a = degOut[x] - degIn[x], b = degOut[y] - degIn[y];
	return a != b ? a > b : x < y;
	});
	tryOrder(order);
	sort(order.begin(), order.end(), [&](int x, int y) {
	return degOut[x] != degOut[y] ? degOut[x] > degOut[y] : x < y;
	});
	tryOrder(order);
	for (int iter = 0; elapsed() < 1.0 && (int)bestPath.size() < n; iter++) {
	for (size_t i = n - 1; i > 0; --i) { size_t j = splitmix64() % (i + 1); swap(order[i], order[j]); }
	tryOrder(order);
	}
	}

	if ((int)bestPath.size() < n && !bestPath.empty())
	improvePath(bestPath, 1.5);

	{
	vector<int> starts;
	int best = 1;
	for (int u = 2; u <= n; u++) if (degOut[u] - degIn[u] > degOut[best] - degIn[best]) best = u;
	starts.push_back(best);
	best = 1;
	for (int u = 2; u <= n; u++) if (degIn[u] < degIn[best]) best = u;
	starts.push_back(best);
	for (int i = 0; i < 50; i++) starts.push_back(randInt(n) + 1);

	for (int s : starts) {
	if (elapsed() > 2.5 \|\| (int)bestPath.size() == n) break;
	auto path = greedyPath(s, 1);
	if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
	if ((int)bestPath.size() == n) break;
	path = greedyPath(s, 0);
	if ((int)path.size() > (int)bestPath.size()) bestPath = move(path);
	}
	}

	if ((int)bestPath.size() < n && !bestPath.empty())
	improvePath(bestPath, 3.0);

	if ((int)bestPath.size() < n) {
	while (elapsed() < 3.5 && (int)bestPath.size() < n) {
	for (int u = 1; u <= n; u++) {
	int s = adjStart[u], l = degOut[u];
	for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(adjData[s + i], adjData[s + j]); }
	s = radjStart[u]; l = degIn[u];
	for (int i = l - 1; i > 0; i--) { int j = splitmix64() % (i + 1); swap(radjData[s + i], radjData[s + j]); }
	}
	auto path = greedyPath(randInt(n) + 1, 0);
	if ((int)path.size() > (int)bestPath.size()) {
	bestPath = move(path);
	if ((int)bestPath.size() < n) improvePath(bestPath, min(elapsed() + 0.3, 3.7));
	}
	}
	}
	}

	if (bestPath.empty()) bestPath.push_back(1);

	printf("%d\n", (int)bestPath.size());
	for (int i = 0; i < (int)bestPath.size(); i++) {
	if (i) putchar(' ');
	printf("%d", bestPath[i]);
	}
	putchar('\n');
	return 0;
	}