#include <bits/stdc++.h>

using namespace std;

int n, minr = 0;
vector<vector<int>> g;
vector<int> ans1, ans2;

void find(int cur, vector<int> a1, vector<int> a2) {
    if (cur == n) {
        if (a1.empty() || a2.empty()) {
            return;
        }
//        for (int i : a1)
//            cout << i << " ";
//        cout << "\n";
//        for (int i : a2)
//            cout << i << " ";
//        cout << "\n\n";
        int sum = 0;
        for (int i = 0; i < a1.size(); ++i) {
            for (int j = 0; j < a2.size(); ++j) {
                sum += g[a1[i]][a2[j]];
            }
        }
        if (minr < sum) {
            minr = sum;
            ans1 = a1;
            ans2 = a2;
        }
        return;
    }
    a1.push_back(cur);
    find(cur + 1, a1, a2);
    a1.pop_back();
    a2.push_back(cur);
    find(cur + 1, a1, a2);
    a2.pop_back();
}

main() {
    cin >> n;
    vector<int> a(n);
    g.resize(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }
    find(0, {}, {});
    cout << minr << "\n";
    vector<int> answer(n);
    for (int i : ans1) {
        answer[i] = 1;
    }
    for (int i : ans2) {
        answer[i] = 2;
    }
    for (int i : answer) {
        cout << i << " ";
    }

}