#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

const int n = 24;

vector<int> gr[n + 1];

pair<int, int> get_rand_pair() {
    int a = rand() % n + 1;
    int b = rand() % n + 1;
    while (a == b) {
        b = rand() % n + 1;
    }
    return {a, b};
}

vector<bool> used(n + 1);
map<pair<int, int>, bool> e;
vector<pair<int, int>> grr;

int check() {
    vector<int> ver;
    while (true) {
        int mx = 0;
        int v = -1;
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                int cnt = 0;
                for (auto to : gr[i]) {
                    if (!e[{i, to}]) {
                        ++cnt;
                    }
                }
                if (cnt > mx) {
                    mx = cnt;
                    v = i;
                }
            }
        }
        if (v == -1) {
            break;
        }
        ver.push_back(v);
        for (auto to : gr[v]) {
            e[{v, to}] = true;
            e[{to, v}] = true;
        }
    }
    return ver.size();
}

int get_bit(int mask, int i) {
    return (mask >> i) & 1;
}

int check_long() {
    int SZ = (1 << n);
    int mn = 10;
    for (int mask = 0; mask < SZ; ++mask) {
        int cnt = 0;
        for (auto ee : grr) {
            int a = ee.first;
            int b = ee.second;
            if (!get_bit(mask, a - 1) && !get_bit(mask, b - 1)) {
                break;
            }
            ++cnt;
        }
        if (cnt == grr.size()) {
            int verts = 0;
            for (int j = 0; j < n; ++j) {
                if (get_bit(mask, j)) {
                    ++verts;
                }
            }
            mn = min(mn, verts);
        }
    }
    return mn;
}

int main() {
    std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    while (true) {
        for (int i = 1; i <= n; ++i) {
            gr[i].clear();
        }
        grr.clear();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                e[{i, j}] = e[{j, i}] = false;
            }
        }
        int m = rand() % (n * (n - 1) / 2);
        set<pair<int, int>> s;
        while (m--) {
            auto p = get_rand_pair();
            while (s.find(p) != s.end()) {
                p = get_rand_pair();
            }
            s.insert(p);
            s.insert({p.second, p.first});
            grr.push_back(p);
            gr[p.first].push_back(p.second);
            gr[p.second].push_back(p.first);
        }
        int greedy = check();
        int ans = check_long();
        if (greedy > ans * 2) {
            cout << greedy << " " << ans << endl;
            vector<vector<int>> dist(n + 1, vector<int> (n + 1));
            for (int i = 1; i <= n; ++i) {
                cout << i << " : ";
                for (auto to : gr[i]) {
                    cout << to << " ";
                }
                cout << endl;
            }
            exit(0);
        }
        cout << greedy << " " << ans << endl;
    }
    return 0;
}