#include using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // using namespace __gnu_pbds; // #include // using Bint = boost::multiprecision::cpp_int; // #include // using namespace atcoder; // https://atcoder.github.io/ac-library/production/document_ja/ using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; constexpr ll mod = 1e9+7; constexpr ll INF = 9'223'372'036'854'775'807/10; #define rep(i,n) for (uint i = 0; i < uint(n); ++i) #define All(a) (a).begin(),(a).end() #define PI acos(-1) vector dx = {1, 0, -1, 0, 1, 1, -1, -1}; vector dy = {0, 1, 0, -1, 1, -1, 1, -1}; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b(const Edge &e) const { return cost > e.cost; } friend ostream& operator<<(ostream& os, const Edge& e) { os << e.from << " " << e.to << " (" << e.cost << ")"; return os; } operator int() const { return to; } }; struct Graph { vector> G; vector edges; Graph() {} Graph(uint n) : G(n) {} void add_edge(uint from, uint to, ll cost = 1, int idx = -1) { G[from].emplace_back(from, to, cost, idx); edges.emplace_back(from, to, cost, idx); } size_t size() const { return G.size(); } vector& operator[](int k) { return G[k]; } friend ostream& operator<<(ostream& os, Graph& g) { for (uint i = 0; i < g.size(); i++) { for (Edge e : g[i]) { cout << e << '\n'; } } return os; } }; struct IoSetup { IoSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << setprecision(15) << fixed; } } iosetup; void print(const vector &v) { for (string s : v) { cout << s << '\n'; } } template void print(const vector> &v, uint w = 0) { for (uint i = 0; i < (uint)v.size(); i++) { cout << right << setw(w) << v[i].first << ' ' << v[i].second << '\n'; } } template void print(const vector &v, uint w = 0) { for (uint i = 0; i < (uint)v.size(); i++) { cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1]; } } template void print(const vector> &v, uint w = 0) { for (uint i = 0; i < (uint)v.size(); i++) { print(v[i], w); } } template void print(const T& arg) { cout << arg << '\n'; } template void print(const T& arg, const Args&... args) { cout << arg << ' '; print(args...); } template istream& operator>>(istream& is, vector& vec) { for (auto& x : vec) is >> x; return is; } /* なもりグラフ (NamoriGraph) 使い方: NamoriGraph ng(n); ng.add_edge(from, to, cost, idx); (0-indexed). 1回の add_edge で2本の辺 (無向グラフ) が追加される ng.build(); ng.forest[i]: 分解された木の i 番目 (0-indexed). from, to は振り直された頂点番号 (0-indexed), cost, idx は元のグラフの辺のコストとインデックス ng.loop_edges[i]: サイクルに属する i 番目 (0-indexed) の辺. from, to, cost, idx は元のグラフをコピー. ng[k]: 頂点 k について, tree_id, 振り直された木の頂点番号 id を返す ng.inv(tree_id, id): tree_id の頂点 id について、元のグラフの頂点番号を返す. 特に id = 0 はサイクル上の頂点 計算量: O(n) 参考: https://ei1333.github.io/library/graph/others/namori-graph.hpp */ struct NamoriGraph { // g: 元のグラフ // forest: サイクルの任意の頂点を根とした木の集合 // loop_edges: サイクルの辺の集合 // iv: 木の番号, 頂点番号 -> 元のグラフの頂点番号 // iv[i][j]: i番目の木のj番目の頂点の元のグラフの頂点番号 // mark_id: 元のグラフの頂点番号 -> 木の番号 // id: 元のグラフの頂点番号 -> 木の頂点番号 Graph g; vector forest; vector loop_edges; vector> iv; vector mark_id, id; NamoriGraph() {} NamoriGraph(uint n) : g(n) {} NamoriGraph(const Graph &g_) : g(g_) {} void add_edge(uint from, uint to, long long cost = 1, int idx = -1) { if (idx == -1) idx = (int)g.edges.size()/2; // 無向グラフなので idx = 辺の数/2 g.add_edge(from, to, cost, idx); g.add_edge(to, from, cost, idx); } struct Info { // tree_id: 木の番号 // id: 木の頂点番号 int tree_id, id; }; // 頂点 k について, tree_id, 振り直された木の頂点番号 id を返す Info operator[](const int &k) const { return (Info){mark_id[k], id[k]}; } // tree_id の頂点 id について、元のグラフの頂点番号を返す // 特に id = 0 はサイクル上の頂点 int inv(int tree_id, int id_) { return iv[tree_id][id_]; } void build() { int n = g.size(); // deg: 次数 // used: 使ったかどうか vector deg(n), used(n); queue que; // 次数が 1 の頂点 (先端) をキューに入れる for (int i = 0; i < n; i++) { deg[i] = g[i].size(); if (deg[i] == 1) { que.emplace(i); used[i] = true; } } while (!que.empty()) { int idx = que.front(); que.pop(); for (Edge &e : g[idx]) { if (used[e.to]) { continue; } // 次数が 1 の頂点の隣接頂点の次数を 1 減らす deg[e.to]--; // 次数が 1 (サイクルに未到達)ならキューに入れる if (deg[e.to] == 1) { que.emplace(e.to); used[e.to] = true; } } } vector edge_used(g.edges.size()/2 + 1); vector loop; // loop を探す for (int v = 0; v < n; v++) { // loop の点を 1 個見つける if (!used[v]) { // それを起点に他のループを探す for (bool update = true; update; ) { update = false; loop.emplace_back(v); // 隣接頂点が loop じゃない or すでに使っている辺ならスキップ for (Edge &e : g[v]) { if (used[e.to] || edge_used[e.idx]) { // edge_used の初期化!!!!!!!!!!! continue; } edge_used[e.idx] = true; // e.idx の辺を使用 loop_edges.emplace_back(v, e.to, e.cost, e.idx); // 使った辺を追加 v = e.to; // 次のループ点 update = true; break; } } break; } } // 起点となる頂点が重複しているので削除 loop.pop_back(); mark_id.resize(n); id.resize(n); for (int i = 0; i < (int)loop.size(); i++) { int pre = loop[(i + (int)loop.size() - 1) % loop.size()]; // 前のループ点 int cur = loop[i]; // 現在のループ点 int nxt = loop[(i + 1) % loop.size()]; // 次のループ点 int sz = 0; // 木の頂点番号 // mark_id: 元のグラフの頂点番号 -> 木の番号 mark_id[cur] = i; // iv[i][j]: i番目の木のj番目の頂点の元のグラフの頂点番号 iv.emplace_back(); iv.back().emplace_back(cur); // 木の頂点番号を振り直す id[cur] = sz++; for (Edge &e : g[cur]) { if (e.to != pre && e.to != nxt) { // サイクル上の点でなければ mark_dfs(e.to, cur, i, sz); // 木の頂点番号を振り直す } } Graph tree(sz); for (Edge &e : g[cur]) { if (e.to != pre && e.to != nxt) { // サイクル上の点でなければ tree[id[cur]].emplace_back(id[cur], id[e.to], e.cost, e.idx); // 木の辺を追加 tree[id[e.to]].emplace_back(id[e.to], id[cur], e.cost, e.idx); // 木の辺を追加 build_dfs(e.to, cur, tree); // 再帰 } } forest.emplace_back(tree); // 木を追加 } } // mark_dfs: 木の頂点番号を振り直す // idx: 現在の頂点 // par: 親 // tree_id: 木の番号 // sz: 木の頂点番号 void mark_dfs(int idx, int par, int tree_id, int &sz) { mark_id[idx] = tree_id; // idx の頂点は tree_id 番目の木に属する iv[tree_id].emplace_back(idx); // tree_id 番目の木の sz 番目の頂点は idx id[idx] = sz++; // idx の頂点は sz 番目の頂点 for (Edge &e : g[idx]) { // idx の隣接頂点について if (e.to != par) { // 親でなければ mark_dfs(e.to, idx, tree_id, sz); // 再帰 } } } void build_dfs(int idx, int par, Graph &tree) { for (Edge &e : g[idx]) { // idx の隣接頂点について if (e.to != par) { // 親でなければ tree[id[idx]].emplace_back(id[idx], id[e.to], e.cost, e.idx); // 木の辺を追加 tree[id[e.to]].emplace_back(id[e.to], id[idx], e.cost, e.idx); // 木の辺を追加 build_dfs(e.to, idx, tree); // 再帰 } } } }; void solve() { ll n; cin >> n; NamoriGraph ng(n); rep(i,n) { ll a, b; cin >> a >> b; a--; b--; ng.add_edge(a, b); } ng.build(); cout << ng.loop_edges.size() << '\n'; for (auto e : ng.loop_edges) { cout << e.idx+1 << ' '; } cout << '\n'; } int main() { uint t = 1; // cin >> t; while (t--) { solve(); } }