#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
void no() {
cout << "impossible\n";
}
int ans[N];
vector<int> adj[N];
bool dfs(int c, int b) {
ans[c] = b;
for (int nxt : adj[c]) {
if (ans[nxt] == -1) {
if (!dfs(nxt, b ^ 1)) return false;
}
else if (ans[nxt] == b) return false;
}
return true;
}
void solve() {
int n, m; cin >> n >> m;
vector<pair<int, int>> v(m);
for (int i = 0; i < m; i++) adj[i].clear();
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b, --a, --b;
v[i] = {a, b};
}
vector<int> cnt(n);
auto add = [&](int l, int r) {
cnt[l]++;
if (r < n-1) cnt[r+1]--;
};
for (auto [l, r] : v) {
if (l <= r) {
add(l, r);
} else {
add(l, n-1);
add(0, r);
}
}
for (int i = 1; i < n; i++) cnt[i] += cnt[i-1];
if (*min_element(cnt.begin(), cnt.end()) < 2) {
no();
return;
}
vector<int> use;
for (int i = 0; i < n; i++) {
if (cnt[i] == 2) {
use.push_back(i);
}
}
fill(ans, ans + m, -1);
bool done_no = 0;
auto solve_hard = [&]() {
auto get_nxt = [&](int i) {
int idx = lower_bound(use.begin(), use.end(), i) - use.begin();
if (idx == sz(use)) return use[0];
return use[idx];
};
// cerr << "use: ";
// for (int x : use) cerr << x << ' ';
// cerr << endl;
vector<vector<int>> mine(n);
for (int i = 0; i < m; i++) {
auto [l, r] = v[i];
// cerr << "> " << l << ' ' << r << endl;
set<int> mark;
if (l <= r) {
int c = get_nxt(l);
while (!mark.count(c) && l <= c && c <= r) {
// cerr << c << ' ';
mark.insert(c);
c = get_nxt((c + 1) % n);
}
// cerr << endl << endl;
} else {
int c = get_nxt(l);
while (!mark.count(c) && (c >= l || c <= r)) {
// cerr << c << ' ';
mark.insert(c);
c = get_nxt((c + 1) % n);
}
// cerr << endl << endl;
}
for (int x : mark) {
mine[x].push_back(i);
}
}
for (int x : use) {
assert(sz(mine[x]) == 2);
int one = mine[x][0], two = mine[x][1];
// cerr << "> " << one << ' ' << two << endl;
adj[one].push_back(two);
adj[two].push_back(one);
}
for (int i = 0; i < m; i++) if (sz(adj[i]) && ans[i] == -1) {
if (!dfs(i, 0)) {
no();
done_no = 1;
return;
}
}
};
if (sz(use)) solve_hard();
if (done_no) return;
vector<int> one;
for (int i = 0; i < m; i++) {
if (ans[i] == 0 || ans[i] == -1) {
one.push_back(i);
}
}
auto reduce = [&]() { // clean one
pair<int, int> big{-1, -1};
vector<vector<int>> who(n);
for (int x : one) {
auto [l, r] = v[x];
who[l].push_back(x);
if (l <= r) {
big = max(big, make_pair(r - l + 1, x));
} else {
big = max(big, make_pair(n - (l - r - 1), x));
}
}
int start = v[big.second].first;
auto dist = [&](int x) {
return (x + n - start) % n;
};
vector<pair<int, int>> fake_v = v;
for (auto& [l, r] : fake_v) {
if (dist(r) < dist(l)) {
r = (start + n - 1) % n;
}
}
int p = (start + 1) % n;
int last = big.second;
vector<int> new_one; new_one.push_back(last);
while (true) {
pair<int, int> best{-1, -1};
while (p != start && dist(p) <= dist(fake_v[last].second) + 1) {
for (int x : who[p]) {
auto [l, r] = fake_v[x];
best = max(best, make_pair(dist(r), x));
}
p = (p + 1) % n;
}
// cerr << "> " << last << ' ' << p << ' ' << best.second << endl;
if (best.second == -1 || dist(fake_v[best.second].second) <= dist(fake_v[last].second)) break;
last = best.second;
new_one.push_back(last);
}
swap(one, new_one);
};
/*
for (int x : one) cerr << x << ' ';
cerr << endl;
*/
reduce();
/*
for (int x : one) cerr << x << ' ';
cerr << endl;
*/
for (int x : one) {
ans[x] = 0;
}
vector<int> two;
for (int i = 0; i < m; i++) {
if (ans[i] != 0) {
ans[i] = 1;
two.push_back(i);
}
}
auto good = [&](vector<int> idx) { // check
vector<int> cnt_check(n);
auto add_check = [&](int l, int r) {
cnt_check[l]++;
if (r < n-1) cnt_check[r+1]--;
};
for (int x : idx) {
auto [l, r] = v[x];
if (l <= r) {
add_check(l, r);
} else {
add_check(l, n-1);
add_check(0, r);
}
}
for (int i = 1; i < n; i++) cnt_check[i] += cnt_check[i-1];
return *min_element(cnt_check.begin(), cnt_check.end()) > 0;
};
if (!good(one) || !good(two)) {
no();
return;
}
cout << "yes\n";
return;
for (int i = 0; i < m; i++) cout << ans[i];
cout << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3009 ms |
3768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
