#line 1 "Library/test/yukicoder/1254.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1254" #line 2 "Library/graph/undirected/two_edge_connected_components.hpp" #include #include // instance: an undirected and not necessarily simple graph class two_edge_connected_component { static constexpr size_t nil = -1; std::vector stack, low, comp; std::vector> graph, tree, memb; void make(size_t now, size_t pre) { size_t ord = low[now] = stack.size(); stack.emplace_back(now); std::vector brid; for (size_t to : graph[now]) { if (to == pre) { pre = nil; continue; } if (low[to] == nil) make(to, now); if (low[to] > ord) { brid.emplace_back(to); graph[to].emplace_back(now); } else if (low[now] > low[to]) low[now] = low[to]; } brid.swap(graph[now]); if (ord == low[now]) { auto pos = stack.end(); tree.resize(tree.size() + 1); auto &adjc = tree.back(); do { --pos; comp[*pos] = memb.size(); for (size_t u : graph[*pos]) adjc.emplace_back(comp[u]); } while (*pos != now); memb.emplace_back(pos, stack.end()); stack.erase(pos, stack.end()); } } public: two_edge_connected_component(size_t n) : comp(n), graph(n) { stack.reserve(n), tree.reserve(n), memb.reserve(n); } void add_edge(size_t u, size_t v) { assert(u < size()), assert(v < size()); graph[u].emplace_back(v), graph[v].emplace_back(u); } void make() { low.assign(size(), nil); for (size_t v = 0; v != size(); ++v) if (low[v] == nil) make(v, nil); } size_t size() const { return graph.size(); } size_t size(size_t i) { assert(i < count()); return memb[i].size(); } size_t count() const { return memb.size(); } size_t operator[](size_t v) const { assert(v < size()); return comp[v]; } const std::vector &bridge(size_t v) const { assert(v < size()); return graph[v]; } const std::vector &component(size_t i) const { assert(i < count()); return memb[i]; } const std::vector> &bridge_tree() const { return tree; } }; // class two_edge_connected_component #line 2 "Library/utils/stream.hpp" #include #include #line 2 "Library/utils/sfinae.hpp" #include #include #include template class trait> using enable_if_trait_type = typename std::enable_if::value>::type; template using element_type = typename std::decay()))>::type; template struct mapped_of { using type = element_type; }; template struct mapped_of::first_type> { using type = typename T::mapped_type; }; template using mapped_type = typename mapped_of::type; template struct is_integral_ext : std::false_type {}; template struct is_integral_ext< T, typename std::enable_if::value>::type> : std::true_type {}; template <> struct is_integral_ext<__int128_t> : std::true_type {}; template <> struct is_integral_ext<__uint128_t> : std::true_type {}; #if __cplusplus >= 201402 template constexpr static bool is_integral_ext_v = is_integral_ext::value; #endif template struct multiplicable_uint { using type = uint_least32_t; }; template struct multiplicable_uint::type> { using type = uint_least64_t; }; template struct multiplicable_uint::type> { using type = __uint128_t; }; #line 6 "Library/utils/stream.hpp" namespace std { template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } template struct tuple_is { static istream &apply(istream &is, tuple_t &t) { tuple_is::apply(is, t); return is >> get(t); } }; template struct tuple_is { static istream &apply(istream &is, tuple_t &t) { return is; } }; template istream &operator>>(istream &is, tuple &t) { return tuple_is, tuple_size>::value - 1>::apply(is, t); } template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { tuple_os::apply(os, t); return os << ' ' << get(t); } }; template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { return os << get<0>(t); } }; template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { return os; } }; template ostream &operator<<(ostream &os, const tuple &t) { return tuple_os, tuple_size>::value - 1>::apply(os, t); } template > typename enable_if::type, string>::value && !is_same::type, char *>::value, istream &>::type operator>>(istream &is, Container &cont) { for (auto &&e : cont) is >> e; return is; } template > typename enable_if::type, string>::value && !is_same::type, char *>::value, ostream &>::type operator<<(ostream &os, const Container &cont) { bool head = true; for (auto &&e : cont) head ? head = 0 : (os << ' ', 0), os << e; return os; } } // namespace std #line 4 "Library/test/yukicoder/1254.test.cpp" int main() { int n; std::cin >> n; two_edge_connected_component becc(n); std::vector> edges(n); for (auto &&[a, b] : edges) { std::cin >> a >> b; --a, --b; becc.add_edge(a, b); } becc.make(); std::vector ans; int id = 0; for (auto &&[a, b] : edges) { ++id; if (becc[a] == becc[b]) ans.emplace_back(id); } std::cout << ans.size() << "\n" << ans << "\n"; }