#define UNIT r5_colour

#include <set>
#include <map>
#include <cstdint>

using graph = std::set< std::pair< int, int > >;

bool has_3colouring( const graph &g, std::map< int, int8_t > &colouring )
{
    for ( auto [ u, v ] : g )
        if ( colouring[ u ] && colouring[ u ] == colouring[ v ] )
            return false;

    for ( auto [ u, v ] : g )
        if ( !colouring[ v ] )
        {
            for ( int c = 1; c <= 3; ++ c )
                if ( colouring[ u ] != c )
                {
                    colouring[ v ] = c;
                    if ( has_3colouring( g, colouring ) )
                        return true;
                    colouring[ v ] = 0;
                }

            return false;
        }

    return true;
}

bool has_3colouring( const graph &g )
{
    std::map< int, int8_t > colouring{ { g.begin()->first, 1 } };
    return has_3colouring( g, colouring );
}

#include "test_main.cpp"