package main import ( "bufio" "fmt" "os" "sort" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) g := make([][]Edge, n) for i := 0; i < n; i++ { var a, b int fmt.Fscan(in, &a, &b) a-- b-- g[a] = append(g[a], Edge{a, b, 1, i}) g[b] = append(g[b], Edge{b, a, 1, i}) } ng := NewNamoriGraph(g) ng.Build() res := []int{} for _, e := range ng.CycleEdges { res = append(res, e.id+1) } sort.Ints(res) fmt.Fprintln(out, len(res)) for _, v := range res { fmt.Fprint(out, v, " ") } } type NamoriGraph struct { // !以环上各个顶点i为根的无向树 Trees []Graph // !基环树中在环上的边,边i连接着树的 root i和i+1 (i>=0) CycleEdges []Edge g Graph iv [][]int markId, id []int } type Edge = struct{ from, to, cost, id int } type Graph = [][]Edge func NewNamoriGraph(g Graph) *NamoriGraph { return &NamoriGraph{g: g} } func (ng *NamoriGraph) Build() { n := len(ng.g) deg := make([]int, n) used := make([]bool, n) que := []int{} for i := 0; i < n; i++ { deg[i] = len(ng.g[i]) if deg[i] == 1 { que = append(que, i) used[i] = true } } for len(que) > 0 { idx := que[0] que = que[1:] for _, e := range ng.g[idx] { if used[e.to] { continue } deg[e.to]-- if deg[e.to] == 1 { que = append(que, e.to) used[e.to] = true } } } mx := 0 for _, edges := range ng.g { for _, e := range edges { mx = max(mx, e.id) } } edgeUsed := make([]bool, mx+1) loop := []int{} for i := 0; i < n; i++ { if used[i] { continue } for update := true; update; { update = false loop = append(loop, i) for _, e := range ng.g[i] { if used[e.to] || edgeUsed[e.id] { continue } edgeUsed[e.id] = true ng.CycleEdges = append(ng.CycleEdges, Edge{i, e.to, e.cost, e.id}) i = e.to update = true break } } break } loop = loop[:len(loop)-1] ng.markId = make([]int, n) ng.id = make([]int, n) for i := 0; i < len(loop); i++ { pre := loop[(i+len(loop)-1)%len(loop)] nxt := loop[(i+1)%len(loop)] sz := 0 ng.markId[loop[i]] = i ng.iv = append(ng.iv, []int{}) ng.id[loop[i]] = sz sz++ ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], loop[i]) for _, e := range ng.g[loop[i]] { if e.to != pre && e.to != nxt { ng.markDfs(e.to, loop[i], i, &sz) } } tree := make(Graph, sz) for _, e := range ng.g[loop[i]] { if e.to != pre && e.to != nxt { tree[ng.id[loop[i]]] = append(tree[ng.id[loop[i]]], Edge{ng.id[loop[i]], ng.id[e.to], e.cost, e.id}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[loop[i]], e.cost, e.id}) ng.buildDfs(e.to, loop[i], tree) } } ng.Trees = append(ng.Trees, tree) } } // 给定原图的顶点rawV,返回rawV所在的树的根节点和rawV在树中的编号. func (ng *NamoriGraph) GetId(rawV int) (rootId, idInTree int) { return ng.markId[rawV], ng.id[rawV] } // 给定树的顶点编号root和某个点在树中的顶点编号idInTree,返回这个点在原图中的顶点编号. // GetInvId(root,0) 表示在环上的顶点root在原图中对应的顶点. func (ng *NamoriGraph) GetInvId(rootId, idInTree int) (rawV int) { return ng.iv[rootId][idInTree] } func (ng *NamoriGraph) markDfs(idx, par, k int, l *int) { ng.markId[idx] = k ng.id[idx] = *l *l++ ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], idx) for _, e := range ng.g[idx] { if e.to != par { ng.markDfs(e.to, idx, k, l) } } } func (ng *NamoriGraph) buildDfs(idx, par int, tree Graph) { for _, e := range ng.g[idx] { if e.to != par { tree[ng.id[idx]] = append(tree[ng.id[idx]], Edge{ng.id[idx], ng.id[e.to], e.cost, e.id}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[idx], e.cost, e.id}) ng.buildDfs(e.to, idx, tree) } } } func max(a, b int) int { if a > b { return a } return b }