/** * date : 2021-08-06 23:16:33 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template inline T Max(const vector &v) { return *max_element(begin(v), end(v)); } template inline T Min(const vector &v) { return *min_element(begin(v), end(v)); } template inline long long Sum(const vector &v) { return accumulate(begin(v), end(v), 0LL); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkinv(vector &v) { int max_val = *max_element(begin(v), end(v)); vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { if (gbit(a, i) != b) a ^= T(1) << i; } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } void dump(const bool& t) { cerr << (t ? "true" : "false"); } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::inf) res = "-inf"; } if constexpr (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::infLL) res = "-inf"; } } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) (void(0)) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define fi first #define se second #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } // namespace atcoder { namespace internal { template struct simple_queue { std::vector payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return int(payload.size()) - pos; } bool empty() const { return pos == int(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } // namespace internal } // namespace atcoder namespace atcoder { template struct mf_graph { public: mf_graph() : _n(0) {} mf_graph(int n) : _n(n), g(n) {} virtual int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = int(pos.size()); pos.push_back({from, int(g[from].size())}); int from_id = int(g[from].size()); int to_id = int(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = int(pos.size()); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } std::vector edges() { int m = int(pos.size()); std::vector result; for (int i = 0; i < m; i++) { result.push_back(get_edge(i)); } return result; } void change_edge(int i, Cap new_cap, Cap new_flow) { int m = int(pos.size()); assert(0 <= i && i < m); assert(0 <= new_flow && new_flow <= new_cap); auto& _e = g[pos[i].first][pos[i].second]; auto& _re = g[_e.to][_e.rev]; _e.cap = new_cap - new_flow; _re.cap = new_flow; } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector level(_n), iter(_n); internal::simple_queue que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < int(g[v].size()); i++) { _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) return res; } level[v] = _n; return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } return flow; } std::vector min_cut(int s) { std::vector visited(_n); internal::simple_queue que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto e : g[p]) { if (e.cap && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } private: int _n; struct _edge { int to, rev; Cap cap; }; std::vector> pos; std::vector> g; }; } // namespace atcoder namespace BipartiteGraphImpl { using namespace atcoder; struct BipartiteGraph : mf_graph { int L, R, s, t; explicit BipartiteGraph(int N, int M) : mf_graph(N + M + 2), L(N), R(M), s(N + M), t(N + M + 1) { for (int i = 0; i < L; i++) mf_graph::add_edge(s, i, 1); for (int i = 0; i < R; i++) mf_graph::add_edge(i + L, t, 1); } int add_edge(int n, int m, long long cap = 1) override { assert(0 <= n && n < L); assert(0 <= m && m < R); return mf_graph::add_edge(n, m + L, cap); } long long flow() { return mf_graph::flow(s, t); } vector> MaximumMatching() { auto es = mf_graph::edges(); vector> ret; for (auto &e : es) { if (e.flow > 0 && e.from != s && e.to != t) { ret.emplace_back(e.from, e.to - L); } } return ret; } // call after calclating flow ! pair, vector> MinimumVertexCover() { auto colored = PreCalc(); vector nl, nr; for (int i = 0; i < L; i++) if (!colored[i]) nl.push_back(i); for (int i = 0; i < R; i++) if (colored[i + L]) nr.push_back(i); return make_pair(nl, nr); } // call after calclating flow ! pair, vector> MaximumIndependentSet() { auto colored = PreCalc(); vector nl, nr; for (int i = 0; i < L; i++) if (colored[i]) nl.push_back(i); for (int i = 0; i < R; i++) if (!colored[i + L]) nr.push_back(i); return make_pair(nl, nr); } private: vector PreCalc() { vector> ag(L + R); vector used(L, false); for (auto &e : mf_graph::edges()) { if (e.from == s || e.to == t) continue; if (e.flow > 0) { ag[e.to].push_back(e.from); used[e.from] = true; } else { ag[e.from].push_back(e.to); } } vector colored(L + R, false); auto dfs = [&](auto rc, int cur) -> void { for (auto &d : ag[cur]) { if (!colored[d]) colored[d] = true, rc(rc, d); } }; for (int i = 0; i < L; i++) if (!used[i]) colored[i] = true, dfs(dfs, i); return colored; } }; } // namespace BipartiteGraphImpl using BipartiteGraphImpl::BipartiteGraph; /** * @brief 二部グラフのフロー * @docs docs/flow/flow-on-bipartite-graph.md */ using namespace Nyaan; void Nyaan::solve() { ini(N); BipartiteGraph g(N,N); rep(i,N){ ini(a,b); --a,--b; g.add_edge(i,a); g.add_edge(i,b); } int fl= g.flow(); if(fl!=N)die("No"); auto es=g.MaximumMatching(); out("Yes"); sort(all(es)); each2(f,s,es)out(s+1); }