結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー みたに
提出日時 2026-05-23 18:07:59
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,087 ms / 2,000 ms
コード長 2,445 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,560 ms
コンパイル使用メモリ 355,548 KB
実行使用メモリ 78,372 KB
最終ジャッジ日時 2026-05-23 18:08:15
合計ジャッジ時間 10,604 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define Yes cout << "Yes" << "\n"
#define No cout << "No" << "\n"
#define rtr0 return(0)
#define all(x) x.begin(), x.end()
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//using mint=static_modint<998244353>;
//using mint=static_modint<1000000007>;
////using mint=modint;
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using ll=long long;
using l3=__int128;
using ull=unsigned long long;
using ld=long double;
using P=pair<ll,ll>;
const ld PI=acos(-1);
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
void yn(bool f){cout<<(f?"Yes":"No")<<endl;}
const vector<int> dx={1,0,-1,0};
const vector<int> dy={0,1,0,-1};
const int inf=1001001001;
const ll INF=1001001001001001001;
ll mod=998244353;



void solve(){
    ll n,m;cin>>n>>m;

    vector<set<ll>> g(n);
    vector<ll> d(n);
    rep(i,m){
        ll u,v;cin>>u>>v;u--;v--;
        g[u].insert(v);
        g[v].insert(u);
        d[u]++;
        d[v]++;
    }

    if(n==3){
        cout<<"Yes"<<endl;
        cout<<1<<endl;
        cout<<2<<endl;
        cout<<3<<endl;
        return;
    }

    priority_queue<ll,vector<ll>,greater<ll>> pq;
    vector<vector<ll>> pa(n,vector<ll>(3,-1));
    rep(i,n)if(d[i]==3){
        pq.push(i);
        ll j=0;
        for(auto x:g[i]){
            pa[i][j]=x;
            j++;
        }
    }

    vector<ll> s;
    while(!pq.empty()){
        auto id=pq.top();pq.pop();
        s.push_back(id);

        for(auto nex:g[id]){
            d[nex]--;
            g[nex].erase(id);
            if(d[nex]==3){
                pq.push(nex);
                ll i=0;
                for(auto x:g[nex]){
                    pa[nex][i]=x;
                    i++;
                }
            }
        }
    }


    reverse(all(s));
    vector<ll> ans(n);
    rep(i,n){
        ll id=0;
        set<ll> st;
        rep(j,4)st.insert(j+1);
        rep(j,3)if(st.count(ans[pa[s[i]][j]]))st.erase(ans[pa[s[i]][j]]);
        ans[s[i]]=*st.begin();
    }
    //cout<<s.size()<<endl;
    //for(auto x:pa){
    //    for(auto y:x){
    //        cout<<y<<" ";
    //    }cout<<endl;
    //}
    cout<<"Yes"<<endl;
    for(auto x:ans)cout<<x<<endl;
}

int main(){
    ll t=1;
    //cin>>t;
    rep(i,t)solve();
}
0