class Graph: #入力定義 def __init__(self,vertex=[]): self.vertex=set(vertex) self.edge_number=0 self.adjacent={v:set() for v in vertex} #頂点の追加 def add_vertex(self,*adder): for v in adder: if not self.vertex_exist(v): self.adjacent[v]=set() self.vertex.add(v) #辺の追加 def add_edge(self,u,v): self.add_vertex(u) self.add_vertex(v) if not self.edge_exist(u,v): self.adjacent[u].add(v) self.adjacent[v].add(u) self.edge_number+=1 #辺を除く def remove_edge(self,u,v): self.add_vertex(u) self.add_vertex(v) if self.edge_exist(u,v): self.adjacent[u].discard(v) self.adjacent[v].discard(u) self.edge_number-=1 #頂点を除く def remove_vertex(self,*vertexes): for v in vertexes: if self.vertex_exist(v): U=self.neighbohood(v) for u in U: self.edge_number-=1 self.adjacent[u].discard(v) del self.adjacent[v] self.vertex.discard(v) #Walkの追加 def add_walk(self,*walk): n=len(walk) for i in range(n-1): self.add_edge(walk[i],walk[i+1]) #Cycleの追加 def add_cycle(self,*cycle): self.add_walk(*cycle) self.add_edge(cycle[-1],cycle[0]) #頂点の交換 def __vertex_swap(self,p,q): self.vertex.sort() #グラフに頂点が存在するか否か def vertex_exist(self,v): return v in self.vertex #グラフに辺が存在するか否か def edge_exist(self,u,v): if not(self.vertex_exist(u) and self.vertex_exist(v)): return False return v in self.adjacent[u] #近傍 def neighbohood(self,v): if not self.vertex_exist(v): return [] return list(self.adjacent[v]) #次数 def degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent[v]) #頂点数 def vertex_count(self): return len(self.vertex) #辺数 def edge_count(self): return self.edge_number #頂点vを含む連結成分 def connected_component(self,v): if v not in self.adjacent: return [] from collections import deque T={u:0 for u in self.vertex} T[v]=1 Q=deque([v]) while Q: u=Q.popleft() for w in self.adjacent[u]: if not T[w]: T[w]=1 Q.append(w) return [x for x in self.adjacent if T[x]] #距離 def distance(self,u,v): from collections import deque inf=float("inf") T={v:inf for v in self.vertex} if u==v: return 0 Q=deque([u]) T[u]=0 while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) if x==v: return T[x] return inf #ある1点からの距離 def distance_all(self,u): from collections import deque inf=float("inf") T={v:inf for v in self.vertex} Q=deque([u]) T[u]=0 while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) return T #最短路 def shortest_path(self,u,v): from collections import deque inf=float("inf") T={v:None for v in self.vertex} if u==v: return [u] Q=deque([u]) T[u]=u while Q: w=Q.popleft() for x in self.adjacent[w]: if not T[x]: T[x]=w Q.append(x) if x==v: P=[v] a=v while a!=u: a=T[a] P.append(a) return P[::-1] return None #何かしらの頂点を選ぶ. def poping_vertex(self): v=self.vertex.pop() self.vertex.add(v) return v def Bridge(G): from collections import deque B=[] ord={v:-1 for v in G.vertex} flag={v:0 for v in G.vertex} nei=G.adjacent #BFSパート for v in G.vertex: if flag[v]: continue k=0 parent={} S=deque([v]) T=[] X=[] while S: u=S.pop() if flag[u]: continue T.append(u) ord[u]=k k+=1 flag[u]=1 if u!=v: X.append((parent[u],u)) for w in nei[u]: if not flag[w]: S.append(w) parent[w]=u low={v:ord[v] for v in T} for w in T[:0:-1]: for x in nei[w]: if w==v or x!=parent[w]: low[w]=min(low[w],low[x],ord[x]) for u,w in X: if ord[u]b: a,b=b,a G.add_edge(a,b) E[(a,b)]=i B=set([(min(*p),max(*p)) for p in Bridge(G)]) T=[E[p] for p in E if p not in B] print(len(T)) write(" ".join(map(str,T)))