#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
auto Subtask1 = [&]() {
return m == n - 1 && (int) g[0].size() == n - 1;
};
auto Subtask2 = [&]() {
return m == n * (n - 1) / 2;
};
auto Subtask3 = [&]() {
bool ok = (m == n - 1);
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (abs(i - j) > 1) {
ok = false;
}
}
}
return ok;
};
auto Tree = [&]() {
return m == n - 1;
};
if (Subtask1()) {
// Subtask 1
cout << 2 * (n - 1) + 1 << '\n';
for (int i = 0; i < n; i++) {
cout << 1 << " ";
}
cout << '\n';
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == 0 || j == i) {
cout << 1 << " ";
} else {
cout << 2 << " ";
}
}
cout << '\n';
for (int j = 0; j < n; j++) {
if (j == 0 || j == i) {
cout << 1 << " ";
} else {
cout << 2 << " ";
}
}
cout << '\n';
}
return 0;
}
/* if (Subtask3()) {
cout << (n - 1) * (n - 1) << '\n';
for (int i = 0; i + 1 < n; i++) {
for (int j = 0; j + 1 < n; j++) {
int col = 2;
for (int k = 0; k < n; k++) {
if (k == j || k == j + 1) {
cout << 1 << " ";
} else {
cout << col << " ";
col += 1;
}
}
cout << '\n';
}
}
return 0;
} */
if (Tree()) {
vector<vector<int>> res;
auto Do = [&](vector<int> v) {
vector<int> seq(n, -1);
for (int i : v) {
seq[i] = 1;
}
int col = 2;
for (int i = 0; i < n; i++) {
if (seq[i] == -1) {
seq[i] = col++;
}
}
res.push_back(seq);
};
vector<bool> del(n);
vector<int> sz(n);
function<void(int, int)> DfsSz = [&](int v, int pv) {
sz[v] = 1;
for (int u : g[v]) {
if (u == pv || del[u]) {
continue;
}
DfsSz(u, v);
sz[v] += sz[u];
}
};
function<int(int, int, int)> FindCentroid = [&](int v, int pv, int n) {
for (int u : g[v]) {
if (u == pv || del[u] || sz[u] * 2 < n) {
continue;
}
return FindCentroid(u, v, n);
}
return v;
};
function<void(int, int)> Dfs = [&](int v, int pv) {
for (int u : g[v]) {
if (u == pv || del[u]) {
continue;
}
Do({u, v});
Dfs(u, v);
}
if (v != pv) {
Do({v, pv});
}
};
function<void(int)> Solve = [&](int v) {
DfsSz(v, v);
v = FindCentroid(v, v, sz[v]);
del[v] = true;
Dfs(v, v);
for (int u : g[v]) {
if (!del[u]) {
Solve(u);
}
}
};
Solve(0);
cout << (int) res.size() << '\n';
for (auto& c : res) {
for (int i = 0; i < n; i++) {
cout << c[i] << " ";
}
cout << '\n';
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:20:8: warning: variable 'Subtask2' set but not used [-Wunused-but-set-variable]
20 | auto Subtask2 = [&]() {
| ^~~~~~~~
Main.cpp:23:8: warning: variable 'Subtask3' set but not used [-Wunused-but-set-variable]
23 | auto Subtask3 = [&]() {
| ^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
344 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
If people start at 0 and 2, then they can avoid each other |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
If people start at 0 and 2, then they can avoid each other |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
1 ms |
344 KB |
Unexpected end of file - int32 expected |
8 |
Halted |
0 ms |
0 KB |
- |