Untitled
unknown
plain_text
2 years ago
7.1 kB
3
Indexable
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define sz(x)(ll) x.size()
#define g_max(x, y) x = max(x, y)
#define g_min(x, y) x = min(x, y)
#define rsz(a, n) a.resize(n)
#define ass(a, n) a.assign(n, 0)
#define YES() cout << "YES\n"
#define Yes() cout << "Yes\n"
#define NO() cout << "NO\n"
#define No() cout << "No\n"
#define endl "\n"
#define print(a) for (auto &x: a) cout << x << " "; cout << endl
#define print_pair(a)
#define FOR(i, fr, to) for (long long i = fr; i <= to; i++)
#define RFOR(i, fr, to) for (long long i = fr; i >= to; i--)
#define pb push_back
#define eb emplace_back
#define is insert
#define F first
#define S second
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using stkll = stack<ll>;
using qll = queue<ll>;
using dqll = deque<ll>;
using sll = set<ll>;
using msll = multiset<ll>;
using mll = map<ll, ll>;
using vsll = vector<sll>;
using sc = set<char>;
using pcll = pair<char, ll>;
ll dr[] = {0, 1, 0, -1}, dc[] = {-1, 0, 1, 0};
const ll INF = 1e18;
ll MOD = 1e9 + 7;
ll mod_add(ll u, ll v, ll mod = MOD) {
u %= mod, v %= mod;
return (u + v) % mod;
}
ll mod_sub(ll u, ll v, ll mod = MOD) {
u %= mod, v %= mod;
return (u - v + mod) % mod;
}
ll mod_mul(ll u, ll v, ll mod = MOD) {
u %= mod, v %= mod;
return (u * v) % mod;
}
ll mod_pow(ll u, ll p, ll mod = MOD) {
ll res = 1;
u %= mod;
if (u == 0) {
return 0;
}
while (p > 0) {
if (p & 1) {
res = (res * u) % mod;
}
p >>= 1;
u = (u * u) % mod;
}
return res;
}
ll mod_inv(ll u, ll mod = MOD) {
u %= mod;
ll g = __gcd(u, mod);
if (g != 1) {
return -1;
}
return mod_pow(u, mod - 2, mod);
}
ll mod_div(ll u, ll v, ll mod = MOD) {
u %= mod, v %= mod;
return mod_mul(u, mod_inv(v), mod);
}
template<class T>
vector<T> operator+(vector<T> a, vector<T> b) {
a.insert(a.end(), b.begin(), b.end());
return a;
}
pll operator+(pll a, pll b) {
pll ans = {a.first + b.first, a.second + b.second};
return ans;
}
template<class A, class B>
ostream &operator<<(ostream &os,
const pair<A, B> &p) {
os << p.first << " " << p.second;
return os;
}
template<class A, class B>
istream &operator>>(istream &is, pair<A, B> &p) {
is >> p.first >> p.second;
return is;
}
template<class T>
ostream &operator<<(ostream &os,
const vector<T> &vec) {
for (auto &x: vec) {
os << x << " ";
}
return os;
}
template<class T>
istream &operator>>(istream &is, vector<T> &vec) {
for (auto &x: vec) {
is >> x;
}
return is;
}
template<class T>
ostream &operator<<(ostream &os,
const set<T> &vec) {
for (auto &x: vec) {
os << x << " ";
}
return os;
}
template<class A, class B>
ostream &operator<<(ostream &os,
const map<A, B> d) {
for (auto &x: d) {
os << "(" << x.first << " " << x.second << ") ";
}
return os;
}
template<class A>
void read_arr(A a[], ll from, ll to) {
for (ll i = from; i <= to; i++) {
cin >> a[i];
}
}
template<class A>
void print_arr(A a[], ll from, ll to) {
for (ll i = from; i <= to; i++) {
cout << a[i] << " ";
}
cout << "\n";
}
template<class A>
void print_arr(A a[], ll n) {
print_arr(a, 0, n - 1);
}
template<class A>
void set_arr(A a[], A val, ll from, ll to) {
for (ll i = from; i <= to; i++) {
a[i] = val;
}
}
template<class A>
void set_arr(A a[], A val, ll n) {
set_arr(a, val, 0, n - 1);
}
const ll N = 1e5 + 10;
ll n, k, q, m;
ll a[N];
string s, s1, s2, s3;
void init() {
}
ll n1[N], n2[N], n3[N], ans[N];
sll adj[N];
ll get_ans() {
set_arr(ans, 0LL, n + 5);
set_arr(n1, 0LL, n + 5);
set_arr(n2, 0LL, n + 5);
set_arr(n3, 0LL, n + 5);
ans[1] = 1;
ll v2 = 0;
for (auto &v: adj[1]) {
n1[v] = 1;
v2 = v;
}
if (!v2) {
return false;
}
ans[v2] = 1;
for (auto &v: adj[v2]) {
n2[v] = 1;
}
ll v3 = 0;
FOR (i , 1, n) {
if (n2[i] && n1[i]) {
v3 = i;
}
}
if (v3 == 0) {
return false;
}
ans[v3] = 1;
for (auto &v: adj[v3]) {
n3[v] = 1;
}
FOR(i, 1, n) {
if (n1[i] && n2[i] && n3[i]) {
return false;
}
if (!n1[i]) {
ans[i] = 1;
continue;
}
if (!n2[i]) {
ans[i] = 2;
continue;
}
if (!n3[i]) {
ans[i] = 3;
}
}
if (!count(ans + 1, ans + 1 + n, 2LL) || !count(ans + 1, ans + 1 + n, 3LL)) {
return false;
}
ll cnt12 = 0, cnt23 = 0, cnt31 = 0;
FOR(i, 1, n) {
for (auto &v: adj[i]) {
if (ans[i] == ans[v]) {
return false;
}
ll ai = ans[i], av =ans[v];
if (ai > av) {
swap(ai, av);
}
if (ai == 1 && av == 2) {
cnt12++;
}
if (ai == 2 && av == 3){
cnt23++;
}
if (av == 3 && ai== 1) {
cnt31++;
}
}
}
ll cnt1 = count(ans + 1, ans + 1 + n, 1LL);
ll cnt2 = count(ans + 1, ans + 1 + n, 2LL);
ll cnt3 = count(ans + 1, ans + 1 + n, 3LL);
cout << cnt12 << " " << cnt23 << " " << cnt31 << "\n";
if (cnt12 != cnt1 * cnt2 || cnt23 != cnt2 * cnt3 || cnt31 != cnt1 * cnt3) {
return false;
}
return true;
}
void single(ll t_id = 0) {
cin >> n >> m;
FOR(i, 1, n) {
adj[i].clear();
}
FOR(i, 1, m) {
ll u, v;
cin >> u >> v;
adj[u].is(v);
adj[v].is(u);
}
if (get_ans()) {
print_arr(ans, 1, n);
} else {
cout << "-1\n";
}
}
void multiple() {
ll t;
cin >> t;
for (ll i = 0; i < t; i++) {
single(i);
}
}
//#endif
#if 0
void multiple() {
while (cin >> n >> m) {
if (n == 0 && m == 0) {
break;
}
single();
}
#endif
int main(int argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
init();
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
freopen("../input.txt", "r", stdin);
multiple();
// single();
return 0;
}
//https://pastecode.io/s/gm8sg8rqEditor is loading...