LAMPS

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define task "LAMPS"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 4e2 + 2;
int m, n, u, v, l, d;
vector<pair<int, int>> s, adj[N];
int ans[N * N / 4];
using Pll = pair<int, int> *;
Pll col[N][N];

void Read()
{
    cin >> m >> n;
    l = m + n;
    while (cin >> u >> v)
    {
        s.push_back({u, v + m});
        adj[u].push_back({v + m, s.size() - 1});
        adj[v + m].push_back({u, s.size() - 1});
    }
}

void Solve()
{
    for (int i = 1; i <= l; ++i)
        d = max(d, (int)adj[i].size());
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= d; ++j)
            col[i][j] = NULL;
    for (int i = 0; i < s.size(); ++i)
    {
        //cerr << i << "\n";
        bool success = 0;
        for (int j = 1; j <= d; ++j)
            if (!col[s[i].first][j] && !col[s[i].second][j])
            {
                success = 1;
                col[s[i].first][j] = new pair<int, int>;
                col[s[i].second][j] = new pair<int, int>;
                col[s[i].first][j]->first = s[i].second;
                col[s[i].second][j]->first = s[i].first;
                col[s[i].second][j]->second =
                    col[s[i].first][j]->second = i;
                ans[i] = j;
                break;
            }
        if (success)
            continue;
        //cerr << "*\n";
        int p[2] = {0, 0};
        for (int j = 1; j <= d; ++j)
        {
            if (!col[s[i].first][j])
                p[0] = j;
            if (!col[s[i].second][j])
                p[1] = j;
            if (p[0] && p[1])
                break;
        }
        //cerr << p[0] << " " << p[1] << "\n";
        //cerr << "#\n";
        int now = s[i].first;
        bool t = 1;
        col[s[i].first][p[0]] = new pair<int, int>;
        *col[s[i].first][p[0]] = {s[i].second, i};
        col[s[i].second][p[1]] = new pair<int, int>;
        *col[s[i].second][p[1]] = {s[i].first, i};
        // cerr << "$\n";
        do
        {
            int cur = col[now][p[t]]->first;
            ans[col[now][p[t]]->second] = p[!t];
            swap(col[now][p[t]], col[now][p[!t]]);
            now = cur;
            t = !t;
        } while (col[now][p[t]]);
        ans[i] = p[1];
        swap(col[now][p[t]], col[now][p[!t]]);
    }
    cout << d << "\n";
    for (int i = 0; i < s.size(); ++i)
        cout << s[i].first << " " << s[i].second - m << " " << ans[i] << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Read();
    Solve();
}