OIG XVII - bot

// https://szkopul.edu.pl/problemset/problem/OzTY7Oyrsp1uVXUt4PCoowjC/site/?key=statement#

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::vector<int> kra[sizik];
int A[sizik], B[sizik];
int n;
int m;
int wchodzi[sizik];
std::vector<int> ans;

int get_for(int v, const std::vector<int>& next, const std::vector<int>& num, bool local_add = false) {
    int local = 0;
    bool passed = false;
    int curr = num[v];
    int nv = v;

    while (true) {
        local++;

        if (local_add) ans.push_back(nv);

        nv = next[nv];

        int prev = curr;
        curr = num[nv];

        if (prev == curr) break;
        if (prev > curr) {
            if (passed) break;
            passed = true;
        }

        if (passed && (curr >= num[v])) {
            break;
        }
    }

    return local;
}

bool check(int t, bool add) {
    std::queue<int> q;
    std::vector<int> dp(n + 1, -1);
    std::vector<int> vis(n + 1);
    std::vector<bool> marked(n + 1);
    std::vector<bool> notCycle(n + 1);
    std::vector<int> next(n + 1);
    std::vector<int> num(n + 1);
    std::vector<int> wchodzi__local_copy(n + 1);
    for (int i = 1; i <= n; i++) {
        wchodzi__local_copy[i] = wchodzi[i];
    }

    for (int i = 1; i <= n; i++) {
        if (wchodzi__local_copy[i] == 0) q.push(i);
    }

    int local_m = m, curr_v = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        vis[x] = curr_v;
        notCycle[x] = true;

        if (dp[x] <= 0) {
            dp[x] = t + 1;
            local_m--;
            if (add) ans.push_back(x);
        }

        dp[A[x]] = std::max(dp[A[x]], dp[x] - 1);

        if (--wchodzi__local_copy[A[x]] == 0) q.push(A[x]);
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i] > 0) continue;

        int left = 0, c = i, len = 0, prev = -1, k2 = 0;
        std::vector<int> cycle;
        while (left > 0 || vis[c] != curr_v) {
            k2++;
            if (vis[c] != curr_v) {
                left = std::max(left, dp[c]);
            }
            if (left-- > 0) marked[c] = true;
            if (vis[c] != curr_v) {
                len++;
                num[c] = len;
                cycle.push_back(c);
            } else {
                if (k2 > 2 * (int)cycle.size() + 7) {
                    left = 0;
                }
            }
            vis[c] = curr_v;
            prev = c;
            c = A[c];
            B[c] = prev;
        }

        curr_v++;
        bool isGood = true;
        int f = -1;
        for (const auto& d : cycle) {
            if (!marked[d]) {
                isGood = false;
                vis[d] = curr_v;
                f = d;
                break;
            }
        }

        if (isGood) continue;

        if (f == -1) std::cout << "WTF_MAX" << std::endl;

        if ((int)cycle.size() <= t) {
            local_m--;
            if (add) ans.push_back(f);
            continue;
        }

        curr_v++;
        int l = i, r = i, w = 0, wpr = 0;
        while (vis[l] != curr_v) {
            vis[l] = curr_v;
            w = std::max(0ll, t - wpr + 1);
            bool isGood1 = false;
            while (w-- > 0 || marked[r]) {
                r = A[r];
                wpr++;
                if (r == l) {
                    isGood1 = true;
                    next[l] = l;
                }
            }

            if (!isGood1) {
                if (wpr >= (int)cycle.size()) {
                    next[l] = l;
                } else {
                    next[l] = r;
                }
            }
            l = A[l];
            wpr--;
        }

        int w1 = t + 1, v = f, mini = INT_MAX, mini_index = -1;
        while (w1-- > 0) {
            int u = get_for(v, next, num);

            if (u < mini) {
                mini = u;
                mini_index = v;
            }

            v = B[v];
        }

        local_m -= mini;

        if (add) {
            get_for(mini_index, next, num, true);
        }
    }

    return local_m >= 0;
}

bool BIG_vis[sizik];
void DFS(int v) {
    if (BIG_vis[v]) return;
    BIG_vis[v] = true;
    for (const auto& u : kra[v]) {
        DFS(u);
    }
}

void solve() {
    std::cin >> n;

    int x = n;
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;

        kra[i].push_back(a);
        A[i] = a;
        if (wchodzi[a]++ == 0) x--;
    }

    std::cin >> m;

    for (int i = 1; i <= n; i++) {
        if (wchodzi[i] == 0) {
            DFS(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!BIG_vis[i]) {
            x++;
            DFS(i);
        }
    }

    if (x > m) {
        std::cout << "NIE\n";
        return;
    }

    int l = 0, r = n;
    while (l < r) {
        int s = (l + r) / 2;

        if (check(s, false)) {
            r = s;
        } else {
            l = s + 1;
        }
    }

    check(l, true);

    std::cout << l << '\n';
    std::cout << ans.size() << '\n';
    for (const auto& a : ans) {
        std::cout << a << " ";
    }
    std::cout << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}