#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e2+10, MOD = 1e9+7;
const ll INF = 1e18+10;
int n, m;
int col[N];
vector<int> og[N];
vector<int> adj[N];
vector<vector<int>> ans;
int par[N];
bool vis[N];
void dfs_build_tree(int c, int p) {
vis[c] = 1;
if (p != -1) {
// cerr << c << ' ' << p << endl;
adj[p].push_back(c), adj[c].push_back(p);
}
for (int nxt : og[c]) if (!vis[nxt]) {
dfs_build_tree(nxt, c);
}
}
void dfs_col(int c, int p) {
// cerr << "> " << c << ' ' << col[c] << endl;
par[c] = p;
for (int nxt : adj[c]) if (nxt != p) {
col[nxt] = col[c] ^ 1;
dfs_col(nxt, c);
}
}
void dfs_par(int c, int p) {
par[c] = p;
for (int nxt : adj[c]) if (nxt != p)
dfs_par(nxt, c);
}
int swim(int b) {
// cerr << "swim(" << b << ")\n";
int cur_good = 0, my_good = -1;
for (int i = 0; i < n; i++) if (col[i] == b) cur_good++, my_good = i;
if (cur_good <= 1)
return my_good;
auto dead = [&](int c) {
return sz(adj[c]) == 1 && col[c] != b;
};
auto alive_leaf = [&](int c) {
if (col[c] != b) return false;
int cnt = 0;
for (int nxt : adj[c])
cnt += !dead(nxt);
assert(cnt);
return cnt == 1;
};
int root = -1;
for (int i = 0; i < n; i++) if (col[i] == b) {
if (alive_leaf(i)) {
root = i;
break;
}
}
int root_child = -1;
for (int nxt : adj[root]) {
if (!dead(nxt)) {
root_child = nxt;
}
}
assert(root != -1 && root_child != -1);
dfs_par(root, -1);
int ops = 2 * n;
for (int rep = 0; rep < ops; rep++) {
if (rep % 2 == 0) { // move from b to ~b
vector<int> v(n, -1);
int cc = 1;
for (int i = 0; i < n; i++) if (col[i] != b && !dead(i)) {
v[i] = cc++;
}
v[root] = v[root_child];
for (int i = 0; i < n; i++) if (col[i] == b && i != root) {
v[i] = v[par[i]];
}
for (int i = 0; i < n; i++) if (v[i] == -1)
v[i] = cc++;
ans.push_back(v);
} else { // move from ~b to b
vector<int> v(n, -1);
int cc = 1;
for (int i = 0; i < n; i++) if (col[i] == b) {
v[i] = cc++;
}
for (int i = 0; i < n; i++) if (col[i] != b && !dead(i)) {
v[i] = v[par[i]];
}
for (int i = 0; i < n; i++) if (v[i] == -1)
v[i] = cc++;
ans.push_back(v);
}
}
// cerr << "swim to: " << root << " with " << sz(ans) << '\n';
return root;
}
vector<int> get_path(int a, int b) {
dfs_par(b, -1);
vector<int> path;
while (true) {
path.push_back(a);
if (a == b) break;
a = par[a];
}
return path;
}
void check() {
vector<pair<int, int>> opts;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
opts.emplace_back(i, j);
for (auto v : ans) {
vector<pair<int, int>> new_opts;
// cerr << "start layer\n";
for (auto [a, b] : opts) {
vector<int> cana, canb;
for (int na : adj[a]) if (v[a] == v[na]) {
cana.push_back(na);
}
if (sz(cana) == 0) cana.push_back(a);
for (int nb : adj[b]) if (v[b] == v[nb]) {
canb.push_back(nb);
}
if (sz(canb) == 0) canb.push_back(b);
for (int x : cana) {
for (int y : canb) {
if (x != b && y != a && x != y) {
// cerr << "from: (" << a << ", " << b << ") to: (" << x << ", " << y << ")\n";
new_opts.emplace_back(min(x, y), max(x, y));
}
}
}
}
sort(new_opts.begin(), new_opts.end());
new_opts.resize(unique(new_opts.begin(), new_opts.end()) - new_opts.begin());
swap(opts, new_opts);
}
assert(sz(opts) == 0);
}
void solve() {
cin >> n;
m = n * (n - 1) / 2;
/*
n = rand() % 20 + 2;
m = n - 1;
*/
// cin >> n >> m;
if (n == 2) {
assert(false);
cout << "1\n1 1\n";
return;
}
srand(time(0));
vector<pair<int, int>> all;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
all.emplace_back(i, j);
assert(sz(all) == m);
for (int i = 0; i < m; i++) {
// int a, b; cin >> a >> b;
auto [a, b] = all[i];
og[a].push_back(b), og[b].push_back(a);
/*
int a = i, b = i + 1;
int a = i + 1, b = rand() % (i + 1);
*/
// cerr << "input: " << a << ' ' << b << endl;
// adj[a].push_back(b), adj[b].push_back(a);
}
dfs_build_tree(0, -1);
dfs_col(0, -1);
/*
for (int i = 0; i < n; i++)
cerr << col[i] << ' ';
cerr << endl;
*/
int a = -1, b = -1;
for (int i = 0; i < n; i++) if (sz(adj[i]) == 1) { // the problem is, something on the color can switch sides after going to the wrong one
a = swim(col[i]);
b = swim(col[i] ^ 1);
a = swim(col[i]);
b = swim(col[i] ^ 1);
break;
}
auto path = get_path(a, b);
for (int i = 1; i < sz(path); i++) {
int x = path[i-1];
int y = path[i];
vector<int> v(n, 1);
v[x] = 2, v[y] = 2;
ans.push_back(v);
}
cout << sz(ans) << '\n';
for (auto v : ans) {
for (int x : v) cout << x << ' ';
cout << '\n';
}
cout.flush();
#ifdef LOCAL
check();
#endif
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
// general idea: two-color the tree, assume that white is more common
// we can cancel out all white nodes by swimming them up to the root:
// - root the tree at a leaf
// - keep swimming the nodes up (make sure that the root swims down to maintain the colors its on)
//
// per turn:
// ~ n ops to bring things to the top (make sure its even)
//
//
//
// if there's both a white and black leaf:
// pull the white things towards the white leaf (n queries)
// pull the black things towards the black leaf (n queries)
// make them touch by bringing them together
// otherwise:
//
//
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
