data_structures_and_algorithms_python/Even Edges.cpp at 5ea817d0a5c206d9e4e8e3614ef31506f86b15ce · shubhamkumar27/data_structures_and_algorithms_python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
    ll t;
    cin >> t;
    while(t--) {
        ll n ,m;
        cin >> n >> m;
        map <ll, ll> mp;
        vector <pair <ll, ll> > v;
        for(ll i = 0 ; i < m ; i++) {
            ll u , x;
            cin >> u >> x;
            mp[u]++;
            mp[x]++;
            v.push_back(make_pair(u,x));
        }

        if(m % 2 == 0) {
            cout << 1 << endl;
            for(ll i = 0 ; i < n ; i++) {
                cout << 1 << " ";
            }
            cout << endl;
        }
        else{
            ll flag = 0;
            ll val ;
            for(ll i = 1 ; i <= n ; i++) {
                if(mp[i] % 2 != 0){
                    flag = 1;
                    val = i;
                    break;
                }
            }
            // 2
            if(flag) {
                cout << 2 << endl;
                for(ll i = 1 ; i <= n ; i++) {
                    if(i == val) {
                        cout << 2 << " ";
                    }
                    else{
                        cout << 1 << " ";
                    }
                }
                cout << endl;
            }
            // 3
            else{
                cout << 3 << endl;
                ll count = 0;
                val = 0;
                for(ll i = 1 ; i <= n ; i++) {
                    if(mp[i] % 2 == 0 && mp[i] > 0) {
                        val = i;
                        break;
                    }
                }

                for(ll i = 0 ; i < m ; i++) {
                    ll p1,p2;
                    p1 = v[i].first;
                    p2 = v[i].second;
                    if(p1 == val || p2 == val) {
                        mp[p1] --;
                        mp[p2]--;
                    }
                }
                ll odd;
                for(ll i = 1 ; i <= n ; i++) {
                    if(mp[i] % 2 != 0) {
                        odd = i;
                        break;
                    }
                }

                for(ll i = 1 ; i <= n ; i++) {
                    if (i == val) {
                        cout << 1 << " ";
                    }
                    else if(i == odd) {
                        cout << 2 << " ";
                    }
                    else{
                        cout << 3 << " ";
                    }
                }
                cout << endl;
            }
        }
    }
    return 0;
}