#include <iostream>
#include <memory>
#include <vector>

static const uint64_t SEED = 0xDEADBEEFull;
static const size_t ROWS = 10000;
static const size_t COLS = 10000;
static const uint32_t COLORS_NUM = 3;

uint32_t LCGRand()
{
    static uint64_t seed = SEED;
    seed = seed * 6364136223846793005 + 1442695040888963407;
    return seed >> 32;
}

struct Block {
	typedef std::shared_ptr<Block> Ptr;
	
	uint32_t color;
	size_t size;
	Ptr redir;
};

int main()
{
	std::vector<Block::Ptr> up_row(COLS);
	size_t max_size = 0;
	
    for (size_t row = 0; row < ROWS; row++) {
    	Block::Ptr left;
    	
    	for (size_t col = 0; col < COLS; col++) {
    		uint32_t color = LCGRand() % COLORS_NUM;
    		
    		Block::Ptr &up = up_row[col];
    		while (up && up->redir)
    			up = up->redir;

    		Block::Ptr cur;
    		if (left && (left->color == color)) {
    			cur = left;
    			
    			if (up && (up->color == color) && (up != left)) {
    				left->size += up->size;
    				up->redir = left;
    			}
    		} else if (up && (up->color == color)) {
    			cur = up;
    		} else {
    			cur = std::make_shared<Block>(Block{color, 0, nullptr});
    		}
    		
    		max_size = std::max(max_size, ++cur->size);
    		left = up = cur;
    	}
    }
	
    std::cout << "Max block size: " << max_size << std::endl;
    return 0;
}