#include using namespace std; struct MaximumMatching { vector< vector > left_to_right, right_to_left; MaximumMatching(int LS, int RS) { left_to_right.resize(LS); right_to_left.resize(RS); } void add_edge(int left, int right); vector< pair > maximum_matching(); }; void MaximumMatching::add_edge(int left, int right) { left_to_right[left].push_back(right); right_to_left[right].push_back(left); } vector< pair > MaximumMatching::maximum_matching() { int L = left_to_right.size(), R = right_to_left.size(); vector match(L,-1); for (int r=0; r from(L,-1); queue Q; for (auto l : right_to_left[r]) { Q.push(l); from[l]=l; } while (!Q.empty() && !found) { int l = Q.front(); Q.pop(); if (match[l]==-1) { found = true; while (from[l]!=l) { match[l] = match[from[l]]; l = from[l]; } match[l]=r; } else { for( auto ll : right_to_left[ match[l] ] ) if (from[ll] == -1) { Q.push(ll); from[ll] = l; } } } } vector< pair > result; for (int i=0; i> N; vector< vector > G(N); vector A, B; set right_options; for (int n=0; n> a >> b; A.push_back(a); B.push_back(b); right_options.insert( a+b ); right_options.insert( a-b ); right_options.insert( a*b ); } vector right_value( right_options.size() ); map right_id; int next_id = 0; for (auto x : right_options) { right_id[x] = next_id; right_value[next_id] = x; ++next_id; } MaximumMatching MM ( N, right_options.size() ); for (int n=0; n