#!/usr/bin/env python3
"""Loopless undirected multigraph: edge blocks and one-vertex-failure queries.
Explicit DFS frames, edge IDs, block/vertex incidence forest, binary lifting.
Standard library, stdout only. No dynamic graph changes or multiple-failure API.
"""
import sys
sys.dont_write_bytecode = True
import json
import random
from itertools import combinations, product


def need(ok, why):
    if not ok: raise ValueError(why)


class Graph:
    def __init__(self, n, edges):
        need(type(n) is int and n >= 0, 'nonnegative exact-integer vertex count')
        need(type(edges) in (list, tuple), 'finite edge list')
        self.n = n
        adj = [[] for _ in range(n)]; saved = []
        for eid, e in enumerate(edges):
            need(type(e) in (list, tuple) and len(e) == 2, 'edge pair')
            u,v = e; self.vertex(u); self.vertex(v)
            need(u != v, 'self loops are outside this interface')
            saved.append((u,v)); adj[u].append((v,eid)); adj[v].append((u,eid))
        self.edges = tuple(saved); self.adj = tuple(tuple(row) for row in adj)

    def vertex(self, v):
        need(type(v) is int and 0 <= v < self.n, 'valid original vertex')


class EdgeBlocks:
    def __init__(self, graph, record=False):
        self.graph = graph; n = graph.n
        self.tin = [-1] * n; self.low = [-1] * n
        self.parent = [None] * n; self.parent_edge = [None] * n
        self.component = [-1] * n; self.components = 0
        self.blocks = []; self.block_vertices = []
        self.edge_block = [-1] * len(graph.edges)
        self.articulation = [False] * n; self.bridges = []
        self.trace = []; self.adjacency_scans = 0
        stamp = [-1] * n; clock = 0
        def emit(parent, child, edge_stack):
            bid = len(self.blocks); block = []; vertices = []
            while True:
                eid = edge_stack.pop(); block.append(eid)
                need(self.edge_block[eid] == -1, 'each edge emitted once')
                self.edge_block[eid] = bid
                for v in graph.edges[eid]:
                    if stamp[v] != bid: stamp[v] = bid; vertices.append(v)
                if eid == self.parent_edge[child]: break
            self.blocks.append(block); self.block_vertices.append(vertices)
            if record: self.trace.append({'event':'emit','parent':parent,'child':child,
                  'low_child':self.low[child],'tin_parent':self.tin[parent],
                  'block':bid,'popped_edges':list(block),'stack_depth':len(edge_stack)})
        for root in range(n):
            if self.tin[root] >= 0: continue
            cid = self.components; self.components += 1
            self.tin[root] = self.low[root] = clock; clock += 1
            self.component[root] = cid
            children = 0; edge_stack = []; frames = [[root,0]]
            while frames:
                u, index = frames[-1]
                if index < len(graph.adj[u]):
                    v,eid = graph.adj[u][index]; frames[-1][1] += 1
                    self.adjacency_scans += 1
                    if eid == self.parent_edge[u]: continue
                    if self.tin[v] < 0:
                        self.parent[v] = u; self.parent_edge[v] = eid
                        self.tin[v] = self.low[v] = clock; clock += 1; self.component[v] = cid
                        if u == root: children += 1
                        edge_stack.append(eid); frames.append([v,0])
                        if record: self.trace.append({'event':'push-tree','edge':eid,'u':u,'v':v,'stack_depth':len(edge_stack)})
                    elif self.tin[v] < self.tin[u]:
                        # Only the descendant->ancestor orientation pushes a non-tree edge.
                        self.low[u] = min(self.low[u],self.tin[v]); edge_stack.append(eid)
                        if record: self.trace.append({'event':'push-back','edge':eid,'u':u,'v':v,'low_u':self.low[u],'stack_depth':len(edge_stack)})
                else:
                    frames.pop(); p = self.parent[u]
                    if p is not None:
                        self.low[p] = min(self.low[p],self.low[u])
                        if self.low[u] > self.tin[p]: self.bridges.append(self.parent_edge[u])
                        if self.low[u] >= self.tin[p]:
                            if p != root: self.articulation[p] = True
                            emit(p,u,edge_stack)
            self.articulation[root] = children > 1
            need(not edge_stack, 'component finishes with an empty edge stack')
        need(all(bid >= 0 for bid in self.edge_block), 'every input edge belongs to a block')
        need(self.adjacency_scans == 2 * len(graph.edges), 'exactly two adjacency scans per edge')


class FailureIndex:
    def __init__(self, blocks):
        self.blocks = blocks; self.graph = blocks.graph; n = self.graph.n
        total = n + len(blocks.blocks)
        self.forest = [[] for _ in range(total)]
        for bid, vertices in enumerate(blocks.block_vertices):
            b = n + bid
            for v in vertices: self.forest[v].append(b); self.forest[b].append(v)
        self.parent = [-1] * total; self.depth = [0] * total; self.component = [-1] * total
        for root in range(n):
            if self.parent[root] != -1: continue
            self.parent[root] = root; self.component[root] = blocks.component[root]; todo = [root]
            while todo:
                u = todo.pop()
                for v in self.forest[u]:
                    if v == self.parent[u]: continue
                    need(self.parent[v] == -1, 'block incidence must be acyclic')
                    self.parent[v] = u; self.depth[v] = self.depth[u] + 1
                    self.component[v] = self.component[u]; todo.append(v)
        self.up = [list(self.parent)]
        for _ in range(1,max(1,total.bit_length())):
            row = self.up[-1]; self.up.append([row[row[v]] for v in range(total)])
        need(sum(map(len,self.forest)) // 2 == total - blocks.components, 'forest edge count')
        need(all(blocks.articulation[v] == (len(self.forest[v]) > 1) for v in range(n)), 'articulation equals incidence degree above one')

    def lca(self, u, v):
        need(type(u) is int and type(v) is int and 0 <= u < len(self.forest) and 0 <= v < len(self.forest), 'forest node')
        if self.component[u] != self.component[v]: return None
        if self.depth[u] < self.depth[v]: u,v = v,u
        gap = self.depth[u] - self.depth[v]; bit = 0
        while gap:
            if gap & 1: u = self.up[bit][u]
            gap >>= 1; bit += 1
        if u == v: return u
        for row in reversed(self.up):
            if row[u] != row[v]: u,v = row[u],row[v]
        return self.parent[u]

    def distance(self, u, v):
        w = self.lca(u,v)
        return None if w is None else self.depth[u] + self.depth[v] - 2*self.depth[w]

    def connected_without(self, u, v, failed):
        for x in (u,v,failed): self.graph.vertex(x)
        if failed in (u,v): return False
        if self.component[u] != self.component[v]: return False
        if self.component[failed] != self.component[u]: return True
        return self.distance(u,v) != self.distance(u,failed) + self.distance(failed,v)

    def components_without(self, failed):
        self.graph.vertex(failed)
        return self.blocks.components + len(self.forest[failed]) - 1

    def path(self, u, v):
        # Diagnostic expanded forest path; not part of the logarithmic query cost.
        w = self.lca(u,v)
        if w is None: return None
        left = []; right = []
        while u != w: left.append(u); u = self.parent[u]
        while v != w: right.append(v); v = self.parent[v]
        return left + [w] + list(reversed(right))


def reach(graph, source, excluded=(), allowed=None):
    excluded = set(excluded)
    if source in excluded: return set()
    permitted = set(range(graph.n)) if allowed is None else set(allowed)
    seen = {source}; todo = [source]
    while todo:
        u = todo.pop()
        for v,_ in graph.adj[u]:
            if v in permitted and v not in excluded and v not in seen: seen.add(v); todo.append(v)
    return seen


def brute_components(graph, failed=None):
    remaining = set(range(graph.n)) - ({failed} if failed is not None else set()); groups = []
    while remaining:
        s = next(iter(remaining)); group = reach(graph,s,() if failed is None else (failed,)); groups.append(group); remaining -= group
    return groups


def brute_blocks(graph):
    # Enumerate maximal vertex-induced connected no-cut subgraphs; dyads count.
    # No DFS times, low values or edge-stack logic are used.
    good = []
    for mask in range(1 << graph.n):
        vertices = {i for i in range(graph.n) if mask >> i & 1}
        if len(vertices) < 2: continue
        if reach(graph,next(iter(vertices)),allowed=vertices) != vertices: continue
        if any(reach(graph,next(iter(vertices-{x})),(x,),vertices) != vertices-{x} for x in vertices): continue
        good.append(vertices)
    maximal = [s for s in good if not any(s < t for t in good)]
    return {frozenset(eid for eid,(u,v) in enumerate(graph.edges) if u in s and v in s) for s in maximal}


def verify(graph):
    blocks = EdgeBlocks(graph); idx = FailureIndex(blocks)
    need({frozenset(es) for es in blocks.blocks} == brute_blocks(graph), 'maximal no-cut induced block oracle')
    count = 0
    for x in range(graph.n):
        groups = brute_components(graph,x)
        need(idx.components_without(x) == len(groups), 'deletion component count')
        for u in range(graph.n):
            reached = reach(graph,u,(x,))
            for v in range(graph.n):
                need(idx.connected_without(u,v,x) == (v in reached), 'single-vertex deletion BFS oracle'); count += 1
    return count


def fixture():
    return Graph(12,[(0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3),
                     (3,6),(6,7),(7,3),(7,8),(7,8),(9,10)])


def checks():
    graphs = queries = 0
    for n in range(6):
        pairs = list(combinations(range(n),2))
        for mask in range(1 << len(pairs)):
            graphs += 1; queries += verify(Graph(n,[e for i,e in enumerate(pairs) if mask >> i & 1]))
    multi = mq = 0
    for n in range(1,5):
        pairs = list(combinations(range(n),2))
        for multiplicities in product(range(3),repeat=len(pairs)):
            multi += 1; mq += verify(Graph(n,[e for e,c in zip(pairs,multiplicities) for _ in range(c)]))
    rng = random.Random(202010); random_queries = 0
    for trial in range(150):
        n = rng.randrange(1,9); edges = []
        for u,v in combinations(range(n),2):
            if rng.randrange(4)==0: edges += [(u,v)] * rng.randrange(1,4)
        random_queries += verify(Graph(n,edges))
    path = Graph(5000,[(i-1,i)for i in range(1,5000)]); idx = FailureIndex(EdgeBlocks(path))
    need(not idx.connected_without(0,4999,2500) and idx.components_without(2500)==2,'deep iterative path')
    bad = 0
    for f in [lambda:Graph(True,[]),lambda:Graph(2,[(0,0)]),lambda:Graph(2,[(0,True)]),
              lambda:Graph(2,[(0,2)]),lambda:idx.connected_without(0,1,5000),
              lambda:idx.components_without(True)]:
        try:f()
        except ValueError:bad+=1
        else:raise AssertionError('invalid input accepted')
    mutable=[[0,1]]; frozen=Graph(2,mutable);mutable[0][1]=0
    need(frozen.edges==((0,1),),'input copied')
    return {'simple_graphs':graphs,'simple_failure_queries':queries,'multigraphs':multi,
            'multi_failure_queries':mq,'random_graphs':150,'random_failure_queries':random_queries,
            'deep_path_vertices':5000,'rejected_inputs':bad,'frozen_input':True}


def main():
    g=fixture();b=EdgeBlocks(g,record=True);q=FailureIndex(b)
    queries=[(0,8,3),(0,8,1),(0,8,7),(4,5,3),(4,8,3),(0,1,2),
             (8,8,7),(8,8,8),(0,10,3),(9,10,3),(11,11,3),(11,0,3)]
    rows=[]
    for u,v,x in queries:
        same=q.component[u]==q.component[v]==q.component[x]
        rows.append({'u':u,'v':v,'failed':x,'connected':q.connected_without(u,v,x),
                     'forest_path':q.path(u,v),'path_lengths':None if not same else [q.distance(u,v),q.distance(u,x),q.distance(x,v)]})
    need([r['connected']for r in rows]==[False,True,False,True,False,True,True,False,False,True,True,False],'fixture outcomes')
    counts=[{'failed':x,'components':q.components_without(x),'incidence_degree':len(q.forest[x])}for x in [2,3,7,11,9]]
    need([r['components']for r in counts]==[4,5,4,2,3],'fixture component counts')
    cycle=Graph(4,[(0,1),(1,2),(2,3),(3,0)]);cq=FailureIndex(EdgeBlocks(cycle))
    need(cq.connected_without(0,2,1)and cq.connected_without(0,2,3)and 2 not in reach(cycle,0,(1,3)),'two failures exceed contract')
    print(json.dumps({'graph':{'n':g.n,'edges':list(enumerate(g.edges))},'tin':b.tin,'low':b.low,
          'dfs_parent':b.parent,'component':b.component,'blocks':b.blocks,'block_vertices':b.block_vertices,
          'edge_block':b.edge_block,'articulation':[v for v in range(g.n)if b.articulation[v]],'bridges':b.bridges,
          'trace':b.trace,'forest_nodes':len(q.forest),'forest':q.forest,'queries':rows,'component_counts':counts,
          'two_failures':{'delete1':True,'delete3':True,'delete_both':False},'checks':checks()},ensure_ascii=False,indent=2))


if __name__=='__main__':main()