|
| 1 | +// @brief Matching on General Graph |
| 2 | +#definePROBLEM"https://judge.yosupo.jp/problem/general_matching" |
| 3 | +#include<bits/stdc++.h> |
| 4 | +#pragma GCC optimize("Ofast,unroll-loops") |
| 5 | +#include"blazingio/blazingio.min.hpp" |
| 6 | +#include"cp-algo/linalg/matrix.hpp" |
| 7 | + |
| 8 | +usingnamespacestd; |
| 9 | +usingnamespacecp_algo::math; |
| 10 | +usingnamespacecp_algo::linalg; |
| 11 | +usingnamespacecp_algo::random; |
| 12 | + |
| 13 | +constint64_t mod =998244353; |
| 14 | +using base = modint<mod>; |
| 15 | + |
| 16 | +voidsolve() { |
| 17 | +int n, m; |
| 18 | + cin >> n >> m; |
| 19 | + matrix<base>T(n); |
| 20 | +for(int i =0; i < m; i++) { |
| 21 | +int u, v; |
| 22 | + cin >> u >> v; |
| 23 | + base x =rng(); |
| 24 | + T[u][v] += x; |
| 25 | + T[v][u] -= x; |
| 26 | + } |
| 27 | +auto [pivots, free] =matrix(T).echelonize(); |
| 28 | + matrix<base>B(size(pivots)); |
| 29 | +for(int i =0; i <ssize(pivots); i++) { |
| 30 | +for(int j =0; j <ssize(pivots); j++) { |
| 31 | + B[i][j] = T[pivots[i]][pivots[j]]; |
| 32 | + } |
| 33 | + } |
| 34 | + B = B.inv().second; |
| 35 | + vector<pair<int,int>> ans; |
| 36 | +for(size_t i =0; i <size(pivots); i++) { |
| 37 | +for(size_t j =0; j <size(pivots); j++) { |
| 38 | +if(T[pivots[i]][pivots[j]] !=0 && B[i][j] !=0) { |
| 39 | + ans.emplace_back(pivots[i], pivots[j]); |
| 40 | + B.eliminate<gauss_mode::reverse>(i, j); |
| 41 | + B.eliminate<gauss_mode::reverse>(j, i); |
| 42 | + B.normalize(); |
| 43 | +for(int k =0; k <ssize(pivots); k++) { |
| 44 | + B[i][k] = B[j][k] =0; |
| 45 | + } |
| 46 | + } |
| 47 | + } |
| 48 | + } |
| 49 | + cout <<size(ans) <<"\n"; |
| 50 | +for(auto [u, v]: ans) { |
| 51 | + cout << u <<'' << v <<"\n"; |
| 52 | + } |
| 53 | +} |
| 54 | + |
| 55 | +signedmain() { |
| 56 | +//freopen("input.txt", "r", stdin); |
| 57 | +ios::sync_with_stdio(0); |
| 58 | + cin.tie(0); |
| 59 | +int t =1; |
| 60 | +// cin >> t; |
| 61 | +while(t--) { |
| 62 | +solve(); |
| 63 | + } |
| 64 | +} |