Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <array>
- #include <set>
- #include <map>
- using namespace std;
- #define int long long
- //const long long INF = 1e18 + 7;
- const int MAXN = 1e5 + 100;
- //const int N = 1e5 + 10;
- //const int MOD = 1e9 + 7;
- int dp[MAXN][2];
- vector<vector<int>> g;
- map<pair<int, int>, pair<int, int>> edges;
- map<pair<int, int>, int> pos;
- void dfs(int v, int p) {
- dp[v][0] = dp[v][1] = 0;
- for (auto to: g[v]) {
- if (to == p) continue;
- dfs(to, v);
- dp[v][0] = max(max(dp[v][0], dp[to][0]), dp[to][1]);
- dp[v][1] = max(dp[v][1], dp[to][0]);
- }
- ++dp[v][1];
- }
- vector<pair<int, pair<int, int>>> ans;
- void get_ans(int v, int p = -1) {
- for (auto to: g[v]) {
- if (to == p) continue;
- if (dp[to][1] > dp[to][0]) {
- int x = min(v + 1, to + 1), y = max(v + 1, to + 1);
- int x1 = edges[make_pair(x, y)].first, y1 = edges[make_pair(x, y)].second;
- ans.emplace_back(make_pair(pos[make_pair(x1, y1)], make_pair(x1, y1)));
- }
- get_ans(to, v);
- }
- }
- bool comp(const pair<int, pair<int, int>>& lhs, const pair<int, pair<int, int>>& rhs) {
- return lhs.first < rhs.first;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, m;
- cin >> n >> m;
- g.resize(n);
- for (int i = 0; i < m; ++i) {
- int u, v;
- cin >> u >> v;
- pair<int, int> tmp = make_pair(min(u, v), max(u, v));
- edges[tmp] = make_pair(u, v);
- pos[tmp] = i;
- --u, --v;
- g[u].emplace_back(v);
- g[v].emplace_back(u);
- }
- dfs(0, -1);
- ans.reserve(m);
- get_ans(0);
- cout << ans.size() << '\n';
- sort(ans.begin(), ans.end(), comp);
- for (int i = 0; i < (int)ans.size(); ++i) {
- cout << ans[i].second.first << ' ' << ans[i].second.second << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment