#include using namespace std; struct Random : std::mt19937 { using std::mt19937::mt19937; using std::mt19937::operator(); static int64_t gen_seed() { return std::chrono::steady_clock::now().time_since_epoch().count(); } Random() : std::mt19937(gen_seed()) {} template auto operator()(Int a, Int b) -> std::enable_if_t, Int> { return std::uniform_int_distribution(a, b)(*this); } template auto operator()(Int a) -> std::enable_if_t, Int> { return std::uniform_int_distribution(0, a - 1)(*this); } template auto operator()(Real a, Real b) -> std::enable_if_t, Real> { return std::uniform_real_distribution(a, b)(*this); } }; // consider shuffling adjacency lists if this gives TLE template struct bipartite_matching { int n_left, n_right; std::vector> g; std::vector match_from_left, match_from_right; std::vector vis; int iteration; bipartite_matching(int _n_left, int _n_right) : n_left(_n_left), n_right(_n_right), g(_n_left), vis(_n_left, 0), match_from_left(_n_left, -1), match_from_right(_n_right, -1), iteration(0) {} // u on left, v on right void add(int u, int v) { g[u].push_back(v); } bool dfs(int u) { vis[u] = iteration; for (auto v : g[u]) { if (match_from_right[v] == -1) { match_from_right[v] = u; match_from_left[u] = v; return true; } } for (auto v : g[u]) { if (vis[match_from_right[v]] != iteration && dfs(match_from_right[v])) { match_from_right[v] = u; match_from_left[u] = v; return true; } } return false; } int get_max_matching() { if constexpr (ToShuffle) { Random rng; for (int i = 0; i < n_left; ++i) std::random_shuffle(std::begin(g[i]), std::end(g[i]), rng); } int new_matchings = 0; int matchings = 0; do { iteration++; new_matchings = 0; for (int u = 0; u < n_left; ++u) if (match_from_left[u] == -1 && dfs(u)) new_matchings++; matchings += new_matchings; } while (new_matchings > 0); return matchings; } std::vector> get_edges() { std::vector> ans; for (int i = 0; i < n_left; ++i) if (match_from_left[i] != -1) ans.emplace_back(i, match_from_left[i]); return ans; } }; using pi=pair; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,l; cin >> n >> m >> l; vector e(l); bipartite_matching matching(n,m); for(int i=0;i> e[i].first >> e[i].second; e[i].first--;e[i].second--; //cerr << e[i].first << "->" << e[i].second << '\n'; matching.add(e[i].first,e[i].second); }//cerr << '\n'; int sz=matching.get_max_matching(); auto edges = matching.get_edges(); set cd,need; for(auto [u,v] : edges){cd.insert({u,v});} while(!cd.empty()){ pi ce=(*cd.begin()); cd.erase(ce); bipartite_matching cm(n,m); for(int i=0;i" << e[i].second << '\n'; cm.add(e[i].first,e[i].second); } int csz=cm.get_max_matching(); //cerr << csz << '\n'; if(sz!=csz){need.insert(ce);} else{ set ncd; auto ced = cm.get_edges(); for(auto [u,v] : ced){ if(cd.find({u,v})!=cd.end()){ncd.insert({u,v});} } cd.swap(ncd); } } for(int i=0;i