Bài B 5.12.2022

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e2 + 5;
constexpr int Inf = 1e9 + 7;

int n, m;
vector<int> adj[N];
int c[N], s[N], res[N];

void Read()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> s[i];

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
}

struct Matrix
{
    int m, n;
    int a[N * 2][N];
    Matrix(const int &m = 0, const int &n = 0) : m(m), n(n)
    {
        memset(a, 0, sizeof a);
    }

    void Elimination(int ans[N]) // ans will store the root
    {
        for (int i = 1; i < n; ++i)
            ans[i] = 0;

        for (int i = 1; i <= m; ++i)
        {
            int k = -1, deg = Inf;

            for (int j = i; j <= m; ++j)
            {
                // Find deg of j-th row

                for (int t = 1; t < n; ++t)
                    if (a[j][t] != 0)
                    {
                        if (deg > t)
                        {
                            deg = t;
                            k = j;
                        }

                        break;
                    }
            }

            if (deg == Inf)
                break;

            // Swap row
            for (int t = 1; t <= n; ++t)
                swap(a[i][t], a[k][t]);

            // Elimination
            for (int j = 1; j <= m; ++j)
                if (j != i)
                {
                    int div = a[j][deg] * a[i][deg] % 3; // a[j][deg] / a[i][deg];

                    for (int t = 1; t <= n; ++t)
                        a[j][t] = ((a[j][t] - a[i][t] * div) % 3 + 3) % 3;
                }
        }

        for (int i = 1; i <= m; ++i)
        {
            int deg = -1;

            for (int j = 1; j < n; ++j)
                if (a[i][j] != 0)
                {
                    deg = j;
                    break;
                }

            if (deg == -1)
            {
                if (a[i][n] != 0)
                {
                    ans[1] = -1;
                    return;
                }
                continue;
            }

            ans[deg] = a[i][n] * a[i][deg] % 3; // a[i][n] / a[i][deg]
        }
    }
};

bool Check(int v)
{
    Matrix f(n, n + 1);

    // Make equations
    for (int i = 1; i <= n; ++i)
    {
        for (auto j : adj[i])
            (++f.a[i][j]) %= 3;

        f.a[i][i] = ((-(int)adj[i].size()) % 3 + 3) % 3;
        f.a[i][n + 1] = ((-c[i]) % 3 + 3) % 3;

        if (s[i] > v)
        {
            ++f.m;
            f.a[f.m][i] = 1;
            f.a[f.m][n + 1] = 0;
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n + 1; ++j)
            f.a[i][j] = ((f.a[i][j] - f.a[n][j]) % 3 + 3) % 3;

    // Guass Elimination
    f.Elimination(res);

    if (res[1] == -1)
        return false;

    return true;
}

void Solve()
{

    int l = -Inf, mid, h = Inf;

    while (l <= h)
    {
        mid = (l + h) / 2;

        if (!Check(mid))
            l = mid + 1;
        else
            h = mid - 1;
    }

    if (l >= Inf)
    {
        cout << -1;
        return;
    }

    cout << l << "\n";

    Check(l);

    for (int i = 1; i <= n; ++i)
        cout << res[i] << " ";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << endl;
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
Input:
4 5 4
2 3
2 5
3 1
4 4

Output:
9
*/