// Maximal-cap extension search. For an m-set Y with L(Y) <= B, let C be a maximum cap inside Y
// (|C| = c >= m - B); every x in Y \ C lies on a secant of C.  Search: for each cap C (one per
// orbit) of size c, all X subset {x : sec_C(x) >= 1}, |X| = m - c, with L(C u X) <= B.
// Usage: ./ext2 capsfile m B [timelimit_sec]
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include <algorithm>
typedef unsigned __int128 u128;
static int THIRD[81][81];
static inline int enc(int a, int b, int c, int d) { return a * 27 + b * 9 + c * 3 + d; }
static inline bool bit(u128 m, int i) { return (m >> i) & 1; }
static long long nodes = 0; static clock_t t0; static double tlimit; static bool timedOut = false;
struct Search {
    u128 S; int pts[81]; int n;
    int t, B; int found;
    int cand[81]; int nc; int secC[81];
    u128 foundSet;
    int marg(int x) { int c = 0; for (int i = 0; i < n; i++) if (bit(S, THIRD[x][pts[i]])) c++; return c / 2; }
    void rec(int idx, int added, int lines) {
        if (found) return;
        if ((++nodes & 0xFFFFF) == 0 && (double)(clock() - t0) / CLOCKS_PER_SEC > tlimit) { timedOut = true; }
        if (timedOut) return;
        if (added == t) { found = 1; foundSet = S; return; }
        int need = t - added;
        if (nc - idx < need) return;
        int lb = lines; for (int k = 0; k < need; k++) lb += secC[cand[idx + k]];
        if (lb > B) return;
        for (int i = idx; i <= nc - need; i++) {
            int x = cand[i]; int m = marg(x);
            if (lines + m > B) continue;
            // remaining bound with this choice
            S |= (u128)1 << x; pts[n++] = x;
            rec(i + 1, added + 1, lines + m);
            n--; S &= ~((u128)1 << x);
            if (found || timedOut) return;
        }
    }
    int run(u128 C, int tt, int BB) {
        S = C; n = 0; for (int i = 0; i < 81; i++) if (bit(C, i)) pts[n++] = i;
        t = tt; B = BB; nc = 0; found = 0;
        for (int x = 0; x < 81; x++) if (!bit(C, x)) { secC[x] = marg(x); if (secC[x] >= 1 && secC[x] <= B) cand[nc++] = x; }
        std::sort(cand, cand + nc, [&](int a, int b) { return secC[a] < secC[b]; });
        rec(0, 0, 0);
        return found;
    }
};
int main(int argc, char** argv) {
    for (int x = 0; x < 81; x++) for (int y = 0; y < 81; y++) {
        int xc[4] = {x / 27, (x / 9) % 3, (x / 3) % 3, x % 3}, yc[4] = {y / 27, (y / 9) % 3, (y / 3) % 3, y % 3};
        THIRD[x][y] = enc((6 - xc[0] - yc[0]) % 3, (6 - xc[1] - yc[1]) % 3, (6 - xc[2] - yc[2]) % 3, (6 - xc[3] - yc[3]) % 3);
    }
    FILE* f = fopen(argv[1], "r"); int m = atoi(argv[2]); int B = atoi(argv[3]); tlimit = argc > 4 ? atof(argv[4]) : 1e9;
    std::vector<u128> caps; char line[4096];
    while (fgets(line, sizeof line, f)) { u128 mm = 0; char* p = strtok(line, " \n"); while (p) { mm |= (u128)1 << atoi(p); p = strtok(nullptr, " \n"); } if (mm) caps.push_back(mm); }
    int c = 0; for (int i = 0; i < 81; i++) if (bit(caps[0], i)) c++;
    int t = m - c;
    printf("%zu caps of size %d, m=%d, B=%d, adding t=%d points (each on >=1 secant)\n", caps.size(), c, m, B, t);
    Search Sch; t0 = clock(); int anyFound = 0;
    for (size_t ci = 0; ci < caps.size(); ci++) {
        if (Sch.run(caps[ci], t, B)) {
            anyFound = 1; printf("FOUND: cap %zu extends to an %d-set with <= %d lines: ", ci, m, B);
            for (int i = 0; i < 81; i++) if (bit(Sch.foundSet, i)) printf("%d ", i); printf("\n"); fflush(stdout);
        }
        if (timedOut) { printf("TIMEOUT at cap %zu after %.0f s, nodes=%lld\n", ci, tlimit, nodes); return 2; }
    }
    printf("%s  (nodes=%lld, %.1f s)\n", anyFound ? "SOME EXTENSION FOUND" : "NONE: no such set with a maximum cap of this size", nodes, (double)(clock() - t0) / CLOCKS_PER_SEC);
    return anyFound;
}