Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

In ABBYY a wonderful Smart Beaver lives. This time, he began to study history. When he…

  1. User

    In ABBYY a wonderful Smart Beaver lives. This time, he began to study history. When he read about the Roman Empire, he became interested in the life of merchants.

    The Roman Empire consisted of n cities numbered from 1 to n. It also had m bidirectional roads numbered from 1 to m. Each road connected two different cities. Any two cities were connected by no more than one road.

    We say that there is a path between cities c1 and c2 if there exists a finite sequence of cities t1, t2, ..., tp (p ≥ 1) such that:

    • t1 = c1
    • tp = c2
    • for any i (1 ≤ i < p), cities ti and ti + 1 are connected by a road

    We know that there existed a path between any two cities in the Roman Empire.

    In the Empire k merchants lived numbered from 1 to k. For each merchant we know a pair of numbers si and li, where si is the number of the city where this merchant's warehouse is, and li is the number of the city where his shop is. The shop and the warehouse could be located in different cities, so the merchants had to deliver goods from the warehouse to the shop.

    Let's call a road important for the merchant if its destruction threatens to ruin the merchant, that is, without this road there is no path from the merchant's warehouse to his shop. Merchants in the Roman Empire are very greedy, so each merchant pays a tax (1 dinar) only for those roads which are important for him. In other words, each merchant pays di dinars of tax, where di (di ≥ 0) is the number of roads important for the i-th merchant.

    The tax collection day came in the Empire. The Smart Beaver from ABBYY is very curious by nature, so he decided to count how many dinars each merchant had paid that day. And now he needs your help. Input

    The first input line contains two integers n and m, separated by a space, n is the number of cities, and m is the number of roads in the empire.

    The following m lines contain pairs of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), separated by a space — the numbers of cities connected by the i-th road. It is guaranteed that any two cities are connected by no more than one road and that there exists a path between any two cities in the Roman Empire.

    The next line contains a single integer k — the number of merchants in the empire.

    The following k lines contain pairs of integers si, li (1 ≤ si, li ≤ n), separated by a space, — si is the number of the city in which the warehouse of the i-th merchant is located, and li is the number of the city in which the shop of the i-th merchant is located.

    The input limitations for getting 20 points are:

    • 1 ≤ n ≤ 200
    • 1 ≤ m ≤ 200
    • 1 ≤ k ≤ 200

    The input limitations for getting 50 points are:

    • 1 ≤ n ≤ 2000
    • 1 ≤ m ≤ 2000
    • 1 ≤ k ≤ 2000

    The input limitations for getting 100 points are:

    • 1 ≤ n ≤ 105
    • 1 ≤ m ≤ 105
    • 1 ≤ k ≤ 105

    Output

    Print exactly k lines, the i-th line should contain a single integer di — the number of dinars that the i-th merchant paid.

    Examples

    Input

    7 8 1 2 2 3 3 4 4 5 5 6 5 7 3 5 4 7 4 1 5 2 4 2 6 4 7

    Output

    2 1 2 0

    Note

    The given sample is illustrated in the figure below.

    Let's describe the result for the first merchant. The merchant's warehouse is located in city 1 and his shop is in city 5. Let us note that if either road, (1, 2) or (2, 3) is destroyed, there won't be any path between cities 1 and 5 anymore. If any other road is destroyed, the path will be preserved. That's why for the given merchant the answer is 2.

  2. DeepSeek Assistant

    We are asked: Given a connected undirected graph with n nodes, m edges. For each of k queries (s, t), we need to count the number of edges whose removal would disconnect s from t. In other words, number of edges that lie on all paths between s and t? Actually, "important for the merchant" is defined as: a road is important if without this road there is no path from warehouse to shop. So an edge e is important for (s,t) if e is a bridge in the sense that it separates s and t: that is, e is a cut edge whose removal increases the number of components such that s and t are in different components. More precisely, e is important for (s,t) if e is an edge that lies on every path between s and t. That is the definition of an edge that separates s and t. Those edges are exactly the edges that are bridges in the graph? Not exactly. If the graph is 2-edge-connected, there might be no such edges. But some edges may be bridges, and for a given pair (s,t), a bridge is important only if it separates s and t; if s and t are on the same side of the bridge, then removal of that bridge does not disconnect them. So we need to count edges that are bridges with respect to separating s and t.

    Alternatively, the set of edges that are important for (s,t) is the set of edges whose removal disconnects s and t. Those are exactly edges that are in every s-t path. In an undirected graph, the set of edges that are in all s-t paths are precisely the bridges of the s-t component? More formally, these edges are the ones that are part of the s-t cut set of size 1? Actually, any edge whose removal disconnects s and t is a bridge of the graph? Not necessarily: It could be a bridge of the whole graph? Consider a graph with two cycles joined by a single edge: that edge is a bridge for the whole graph. Its removal disconnects the graph into two components. For any pair (s,t) that lie on opposite sides, that bridge is important; for pairs on same side, not important. However, there could be edges that are not bridges of the whole graph but still are important for a specific pair? Let's think: Suppose we have a graph where s and t are connected via two edge-disjoint paths. Then removing any single edge would not disconnect them, because there is an alternate path. So for an edge to be important for (s,t), it must be that all s-t paths go through that edge. That edge must lie on every s-t path. This is equivalent to the edge being a bridge in the subgraph consisting of all edges that lie on some s-t path? Actually, if we consider the graph, the condition that e lies on every s-t path means that there is no alternative s-t path avoiding e. This is exactly the condition that e is a cut edge separating s and t. But it's not necessarily a bridge of the whole graph: It could be a bridge in the graph after removing some parts? Wait, if e is not a bridge of the whole graph, then there exists some pair of vertices (u,v) such that removing e does not disconnect u and v. However, for e to be important for (s,t), we require that s and t become disconnected upon removal of e. This property is exactly that e is a bridge of the graph? Actually, the definition of a bridge: an edge whose removal increases the number of connected components. That is, for a bridge e, there exist vertices that become disconnected. But if e is a bridge, then the graph becomes two components. For any two vertices that lie in different components after removal, e was crucial. However, if e is not a bridge, its removal does not disconnect any pair of vertices (the graph remains connected). So for e to disconnect s and t, e must be a bridge. But could there be a scenario where e is not a bridge globally, yet its removal disconnects s and t? Suppose the graph is globally 2-edge-connected (no bridges), but there might be an edge whose removal disconnects s and t? If the graph remains connected overall, then after removing e, s and t might still be connected via another path. However, if s and t are in the same component, the graph is still connected, so s and t remain connected. Actually, if the graph remains connected, then all vertices are still connected, so s and t are connected. Therefore, if e is not a bridge, its removal does not increase the number of components; hence the graph remains one component, so s and t remain in the same component. So they are still connected. So only bridges can disconnect some pairs. However, consider a bridge e that when removed splits the graph into two components A and B. Then for any s in A and t in B, e is important; for s,t both in A or both in B, e is not important. So important edges for a given query are exactly the bridges that lie on the unique path between s and t in the bridge-tree (the tree formed by contracting 2-edge-connected components). Wait, the bridges of the graph form a forest? Actually, in a connected graph, the bridges form a tree (or more generally, a forest) when we contract each 2-edge-connected component (i.e., each maximal bridgeless subgraph) into a node. This is called the bridge-block tree or the 2-edge-connected components tree. Since the graph is connected, the resulting tree is a tree. Then any two vertices s and t belong to some 2-edge-connected components (possibly the same). The path between their components in the bridge-block tree consists of bridges. The set of bridges that are important for (s,t) is exactly the set of bridges on the unique path between the components containing s and t. Because if you remove any bridge on that path, the two components become separated and s and t become disconnected. Conversely, bridges not on that path do not affect connectivity between s and t (they are either in subtrees that are not on the path). So the answer for each query is the number of bridges on the path between the components containing s and t in the bridge-block tree.

    Thus we need to: compute all bridges in the graph, partition vertices into 2-edge-connected components (using bridge detection). Then build a tree where each node corresponds to a component, and edges correspond to bridges (each bridge connects two components). Then for each query (s,t), find the components id_s and id_t. If they are the same, answer is 0. Otherwise, answer = distance (number of edges) between the two component nodes in the tree.

    So we need to answer many queries (k up to 1e5) with n,m up to 1e5. So we can precompute bridges (using DFS lowlink in O(n+m)). Then assign component IDs (via DFS or BFS avoiding bridges). Then build tree of size comp_n <= n. Then preprocess for LCA to answer distance queries quickly (distance = depth[u] + depth[v] - 2*depth[lca]). Since tree size up to 1e5, LCA using binary lifting O(log N) per query is fine.

    Alternatively, we could use a simpler method: after building the tree, compute depth and parent arrays and answer each query via LCA.

    Edge cases: Graph is connected initially, so tree is connected.

    Thus solution:

    1. Read n,m.
    2. Build adjacency list with edge indices (to handle parallel? but given no multiple edges, but we still need to handle edge identification for bridges). We'll store edges as (v, idx) and also keep array of (u,v) for each index.
    3. Find bridges using standard DFS: low[u], disc[u], parent edge index. Use timer. For each edge (u,v) if low[v] > disc[u] then it's a bridge.
    4. After bridges identified, run BFS/DFS to assign component id to each vertex, skipping bridges. i.e., we traverse graph but only move through non-bridge edges. Each connected component of that subgraph (ignoring bridges) is a 2-edge-connected component (since removal of bridges splits them). Actually, note: 2-edge-connected components are defined as maximal subgraphs without bridges; but also there is notion that inside a component, any two vertices are 2-edge-connected (there are two edge-disjoint paths). But our approach: after identifying bridges, we remove them, then each connected component of remaining graph is a 2-edge-connected component. However, is that always correct? Yes, because bridges are exactly edges whose removal disconnects the graph. If we remove all bridges, each connected component is bridgeless (maximal?). Actually, there could be a component that is not 2-edge-connected? Consider a graph with a bridge and a cut vertex but no bridges inside. After removing bridges, the remaining graph may still have articulation points, but that's fine; 2-edge-connected components are about edge connectivity, not vertex connectivity. So yes, components after removing bridges are the 2-edge-connected components. So we can assign comp_id per vertex via DFS ignoring bridges.
    5. Build tree: For each bridge (u,v), we have components comp[u] and comp[v]. Since u and v are connected by a bridge, comp[u] != comp[v]. Add edge between them in the tree.
    6. The tree may have multiple edges? Since the original graph has no multiple edges, but could there be multiple bridges connecting same pair of components? Possibly? Suppose there are two distinct bridges directly connecting two 2-edge-connected components? Is that possible? In a graph, if there are two bridges connecting the same two components, then neither would be a bridge? Actually, if there are two edges between the same two components, then removing one edge still leaves the other, so both components remain connected; thus neither is a bridge. So in a graph with no parallel edges, you cannot have two bridges connecting the same pair of vertices (since they'd be parallel edges). But could you have two bridges connecting two distinct vertices that belong to the same two components? Example: Component A contains vertices a1,a2; component B contains vertices b1,b2. Edges: (a1,b1) and (a2,b2). Both are bridges? Check: If we remove (a1,b1), are there still a path from A to B? Possibly via (a2,b2) if that edge is present. So then (a1,b1) is not a bridge because there is still connection via (a2,b2). Indeed, any edge whose removal disconnects the graph must be the only connection between two parts; if there are two distinct edges connecting the same two parts, removing one leaves the other, so the graph remains connected; thus neither is a bridge. So in a simple graph (no multiple edges), each bridge corresponds to a unique cut that separates the graph into two components, and each such cut corresponds to exactly one bridge? Actually, a cut may have multiple bridges if they are all bridges? If there are multiple bridges connecting the same two parts, as argued, they would not be bridges because each one has an alternative. So indeed, each bridge corresponds to a unique edge that is the sole connection between two 2-edge-connected components. Thus the tree constructed will be simple (no multiple edges). So we can just build an adjacency list for the tree.
    7. Preprocess LCA for the tree. Since tree size up to 1e5, we can do binary lifting with log2(1e5) ~ 17, but safe to use 17 or 20.
    8. For each query, read s, l (where l is shop), get cs = comp[s], ct = comp[l]. If cs == ct, answer 0. Else, compute distance = depth[cs] + depth[ct] - 2*depth[lca(cs,ct)].
    9. Output each answer.

    Now we need to careful: The graph is connected, so the tree is connected.

    Complexities: O(n + m) for bridge finding and component assignment, O(comp_n log comp_n) for LCA preprocessing, O(k log comp_n) for queries.

    Now we must implement.

    Double-check bridge detection: Use DFS with timer, disc[u], low[u]. For each neighbor v: if not visited: parent edge index e, DFS(v). low[u] = min(low[u], low[v]). if low[v] > disc[u], then edge e is a bridge. else if (v != parent) ignoring immediate parent edge (using edge index), then low[u] = min(low[u], disc[v]). We'll store edges in an array: edges[i] = (u,v). We'll have adjacency list: for each node, list of (neighbor, edge_id). When DFS, we pass current edge id to avoid using the back edge to parent.

    Implementation details:

    • We'll use 0-index or 1-index? Input nodes are 1..n. We'll use 1-index arrays.
    • m up to 1e5, so adjacency list vector<vector<pair<int,int>>> adj(n+1).
    • Bridge detection: vector isBridge(m, false). We'll assign each edge an index 0..m-1.

    After DFS, we have isBridge flags.

    Now component assignment: We'll do a BFS/DFS through non-bridge edges. We'll have comp array of size n+1 initialized -1. For each vertex not assigned, start a new component ID, and do a stack/queue, traversing to neighbors only if edge is not a bridge. For each neighbor, if not assigned, assign same comp ID. This yields comp IDs.

    Number of components: comp_cnt.

    Now build tree: vector<vector> tree(comp_cnt). For each bridge edge (u,v) (with isBridge[i] true), get cu = comp[u], cv = comp[v]. Add edge between cu and cv: tree[cu].push_back(cv), tree[cv].push_back(cu).

    Now we have a tree. Choose root (say 0). Compute depth and up table via DFS.

    Binary lifting: LOG = ceil(log2(comp_cnt)) + 1. Use up[comp_cnt][LOG]. Actually up[v][j] = 2^j-th ancestor.

    We'll do DFS from root (0) (or 1). We'll compute depth and parent (up[v][0]). Then fill up table.

    LCA function: if depth[u] < depth[v] swap. lift u to depth of v. if u==v return u. for j from LOG-1 down to 0: if up[u][j]!=up[v][j]: u=up[u][j]; v=up[v][j]; return up[u][0].

    Distance = depth[u] + depth[v] - 2*depth[lca].

    Now answer queries.

    Check example:

    n=7, m=8.

    Edges: 1-2 2-3 3-4 4-5 5-6 5-7 3-5 4-7

    Let's compute bridges. Graph looks like: 1-2-3-4-5-6 and 5-7, 3-5, 4-7. So there is a cycle? 3-4-7-5-3? Actually, 3-4,4-7,7-5,5-3 forms a cycle (3-4-7-5-3). Also 4-5 is present? Actually, edge 4-5 is given: 4-5. So cycle 3-4-5-3 plus 4-7 and 5-7, maybe more cycles. Let's analyze: edges: 1-2,2-3 are like a chain to a cycle area. The subgraph from 3,4,5,7: edges: 3-4,4-5,5-3? Actually, 5-3 is given as edge 3-5? Yes, 3-5 is edge. So triangle 3-4-5-3 (since 3-4,4-5,5-3). Additionally, 4-7 and 5-7 edges: 4-7 and 5-7. That creates cycles: 3-4-7-5-3 (if 3-5 exists). So there are multiple cycles, meaning no bridges inside that region. Edge 1-2? Possibly a bridge? Check: If we remove 1-2, graph becomes disconnected? Node 1 becomes isolated from rest? Since 1 is only connected to 2. So yes, 1-2 is a bridge. Similarly, 2-3? Node 2 is connected to 1 and 3. If we remove 2-3, then 1-2 become isolated from rest? Actually, 1 and 2 would be separated from rest because 2's only other connection is 3, so removal would separate component {1,2} from the rest. But check: there might be alternate path from 2 to 3? 2-... can go 2-1? no, 1 only to 2. So no alternate. So 2-3 is a bridge as well. What about 5-6? Node 6 only connects to 5. So 5-6 is a bridge. Others: 3-4,4-5,5-7,4-7,3-5 are not bridges because they are part of cycles. So bridges: (1-2), (2-3), (5-6). Possibly also? Let's confirm: 5-6 is a bridge; after removal, 6 becomes isolated from rest? Actually, 6 is only connected to 5, so yes. So we have 3 bridges.

    Now components after removing bridges: Component A: vertices {1}? Actually, if we remove bridges, edge 1-2 is removed, so vertex 1 isolated => comp1 = {1}. Component B: vertex {2}? Since after removing bridges, edges remaining: we removed 1-2,2-3,5-6. So edges left: 3-4,4-5,5-7,4-7,3-5. Vertex 2 is not connected to anyone because its only neighbor 1 and 3 are both removed (2-3 removed). So vertex 2 is isolated: comp2 = {2}. Component C: vertices {6} isolated: comp6 = {6}. Component D: vertices {3,4,5,7} because they are connected through remaining edges. So we have 4 components: comp1, comp2, comp6, compD.

    Now build tree: bridges connect components:

    • Bridge (1-2) connects comp1 and comp2.
    • Bridge (2-3) connects comp2 and compD.
    • Bridge (5-6) connects compD and comp6.

    Thus tree: comp1 -- comp2 -- compD -- comp6. That's a path of length 3 edges.

    Now queries: 1 5: s=1 (comp1), t=5 (compD). Path in tree: comp1 - comp2 - compD => 2 edges. Answer 2. matches sample. 2 4: s=2 (comp2), t=4 (compD). Path: comp2 - compD => 1 edge. answer 1. 2 6: s=2 (comp2), t=6 (comp6). Path: comp2 - compD - comp6 => 2 edges. answer 2. 4 7: s=4 (compD), t=7 (compD). same component => 0. answer 0. matches.

    Great.

    Now we need to implement.

    Edge Cases:

    • n=1, m=0? But graph must be connected, so if n=1, m=0, it's ok (trivial). But constraints guarantee m may be at least n-1? Not necessarily, but for connectivity, n=1 is fine. Then there are no bridges. Component count = 1. Tree has single node. All queries (s=1,l=1) answer 0. If s!=l? but both are 1, so fine.

    • Graph is a tree (all edges are bridges). Then each vertex is its own component? Wait, if all edges are bridges, then after removing bridges, no edges remain, so each vertex is isolated component. So comp count = n. Tree built from bridges will be exactly the original tree. Then answer for query (s,t) is number of edges on path between s and t in original tree. That's correct because each edge is a bridge and lies on all paths. So answer is distance. Good.

    • Graph has cycles. Works.

    Now we need to handle up to 1e5. We'll implement DFS for bridge detection using recursion. Could cause stack overflow if recursion depth is up to 1e5. Use iterative DFS? In many contests, recursion with 1e5 is borderline but often works with sys.setrecursionlimit in Python. However, here we are writing C++ solution? The problem expects a solution in some language? Usually in such tasks, we can use C++ with recursion depth up to 1e5; default stack may be small. But we can increase stack limit or implement iterative DFS. In competitive programming in C++, it's common to set recursion limit via #define or use iterative. We'll implement recursive but careful to increase stack? On many judges, default recursion depth may cause segfault if deep recursion >~1e5. So we might implement iterative DFS for bridge detection using explicit stack. However, it's easier to write recursive and hope it's fine. Alternatively, we can use adjacency and recursion with sys.setrecursionlimit if Python, but problem likely expects C++? Actually, the prompt: "In ABBYY a wonderful Smart Beaver lives." This is from Codeforces problem? Probably from Codeforces Round? Usually C++ is used. But I'm ChatGPT giving solution. I'll provide a C++ solution. To be safe, I'll implement recursion but maybe add #pragma comment to increase stack? Or simply note that the recursion depth in DFS is at most n which is 1e5; on many judges (like Codeforces), recursion depth of 1e5 may cause stack overflow. They often recommend using iterative or set ulimit -s unlimited? But for Codeforces, many participants use recursion with depth 2e5 and it's fine because the stack size is around 256 MB? Actually, Codeforces has a default stack size of 256 MB? I'm not sure. Typically, recursion depth of 1e5 in C++ might cause segfault because default stack is 8 MB? 1e5 stack frames with local variables could exceed 8 MB. So we need to be careful.

    We can implement iterative DFS for bridge detection. But building an iterative lowlink algorithm is a bit more complex but doable. Alternatively, we can use recursion but use #include <sys/resource.h> and set stack size at start. Many contestants do that. But to be safe, I'll implement iterative bridge detection using algorithm: perform DFS with parent edge index and maintain arrays. Actually, we can use a stack to simulate recursion, tracking state. There is known iterative algorithm for articulation points and bridges using stack and handling low values post-order.

    Simplify: We can use Tarjan's algorithm with recursion; I think it's acceptable if we increase recursion limit? In C++, we can't increase stack size programmatically easily without platform-specific calls. However, we can use #pragma comment(linker, "/STACK:268435456") on Windows or use sys/resource.h on Linux. For generic solution, we can write recursion; many solutions on Codeforces for n=1e5 with recursion pass because of optimizations (using vector and iterative? Actually, many participants use recursion for DFS and pass). Let's check: In Codeforces problem "A and B and Interesting Substrings"? Not sure. I recall that recursion depth of 1e5 is often okay if you compile with -O2 and use -Wl,--stack,16777216? Actually, Codeforces uses Windows? Codeforces uses Windows for MSVC? But many participants use GCC with -std=c++17 and they often use recursion for 2e5 depth and it works? I've seen many solutions using recursion for DFS on trees of size 2e5 and they pass. Possibly because the stack frame for a simple recursive function is small, and the default stack on Codeforces is large enough (maybe 256 MB). But I'm not 100% sure. For safety, we can implement iterative.

    Given time, we can implement recursion and mention increasing stack size. Since this is a solution explanation, we can just provide code with recursion and note to set stack limit.

    But the answer expected is just code? The user says "In ABBYY a wonderful Smart Beaver lives. This time, he began to study history...". That's the problem statement. They likely want a solution. I'll provide a C++ solution with recursion and maybe add:

    #ifdef LOCAL
    ...
    #else
    #define NDEBUG
    #endif
    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        // code
    }
    

    And in the DFS, use recursion.

    But for bridge detection, we need to avoid recursion depth > n. In worst-case, a path of length 1e5 could cause recursion depth 1e5, which might be okay. Many judges allow recursion up to a few hundred thousand. So we'll go with recursion.

    Now implement step by step.

    Pseudo-code:

    int n, m;
    vector<pair<int, int>> edges; // store edges
    vector<vector<pair<int, int>>> adj; // neighbor, edge_id
    
    vector<int> disc, low;
    vector<bool> isBridge;
    int timer = 0;
    
    void dfs(int u, int parent_edge) {
        disc[u] = low[u] = ++timer;
        for (auto &[v, id] : adj[u]) {
            if (id == parent_edge) continue;
            if (!disc[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    isBridge[id] = true;
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }
    

    Note: For undirected graphs, we treat visited neighbor as back edge if it's not the parent edge. However, using disc[v] not zero indicates visited, but it may also be ancestor. But careful: If we have already visited v but not necessarily finished? In DFS recursion, when we encounter a back edge to an ancestor, disc[v] is set and low[u] can use disc[v]. That's fine. However, we must avoid using the edge to parent (the one we came from) as a back edge because it's not a back edge. So using parent_edge id works.

    Now after DFS, we have isBridge.

    Now assign component ids:

    vector<int> comp(n+1, -1);
    int comp_cnt = 0;
    function<void(int, int)> dfs_comp = [&](int u, int cid) {
        comp[u] = cid;
        for (auto &[v, id] : adj[u]) {
            if (isBridge[id]) continue; // skip bridges
            if (comp[v] == -1) {
                dfs_comp(v, cid);
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (comp[i] == -1) {
            dfs_comp(i, comp_cnt++);
        }
    }
    

    Now comp_cnt is number of components.

    Build tree:

    vector<vector<int>> tree(comp_cnt);
    for (int i = 0; i < m; i++) {
        if (isBridge[i]) {
            int u = edges[i].first, v = edges[i].second;
            int cu = comp[u], cv = comp[v];
            tree[cu].push_back(cv);
            tree[cv].push_back(cu);
        }
    }
    

    Now LCA preprocess:

    int LOG = 0;
    while ((1 << LOG) <= comp_cnt) LOG++;
    vector<vector<int>> up(comp_cnt, vector<int>(LOG, -1));
    vector<int> depth(comp_cnt, 0);
    
    function<void(int, int)> dfs_tree = [&](int u, int p) {
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            if (up[u][j-1] != -1) up[u][j] = up[up[u][j-1]][j-1];
            else up[u][j] = -1;
        }
        for (int v : tree[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs_tree(v, u);
        }
    };
    int root = 0; // or any node with degree >0? but if comp_cnt=1, tree has one node; we still need to call dfs_tree(0, -1) but will it cause issues? We'll handle.
    if (comp_cnt > 0) {
        dfs_tree(root, -1);
    }
    

    But root may not be 0 if comp_cnt=0? impossible. So okay.

    LCA function:

    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if (diff & (1 << j)) {
                u = up[u][j];
            }
        }
        if (u == v) return u;
        for (int j = LOG-1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    };
    

    Now answer queries:

    int k; cin >> k;
    while (k--) {
        int s, t; cin >> s >> t;
        int cs = comp[s], ct = comp[t];
        if (cs == ct) {
            cout << "0\n";
        } else {
            int l = lca(cs, ct);
            int dist = depth[cs] + depth[ct] - 2 * depth[l];
            cout << dist << "\n";
        }
    }
    

    That's all.

    Now check complexity: O((n+m) + (comp_cnt log comp_cnt) + k log comp_cnt).

    Potential pitfalls:

    • The DFS for bridges must be called on each component? Since graph is connected, one DFS covers all. But we should loop over all vertices just in case (though connectivity is guaranteed, we can just call from 1). We'll do for (int i=1;i<=n;i++) if(!disc[i]) dfs(i, -1). That's fine.

    • The dfs recursion: ensure we pass parent_edge id. For root, parent_edge = -1.

    • The isBridge vector size m.

    • The component DFS (dfs_comp) recursion also could be deep, but again depth could be up to n. However, after removing bridges, the graph may still be deep? But components are bridgeless, they can be large and possibly have depth up to n (e.g., a long cycle? Actually a cycle has depth up to n/2 in DFS, but recursion depth could be up to n if we do naive recursion on cycle? If we DFS on a cycle, recursion depth will be the number of nodes if we go around and back? But we can avoid deep recursion by using iterative BFS. To be safe, we can use stack for component assignment as well. However, recursion depth could still be high. But we can replace both DFS with iterative to be safe. But many participants use recursion.

    Given constraints, we can implement iterative component assignment: use stack manually. But easier: we can use BFS (queue) to assign components: start from unassigned node, assign ID, push to queue; for each node, iterate neighbors, if edge not a bridge and neighbor unassigned, assign and push. That's BFS, which avoids recursion depth. We'll implement BFS for component assignment.

    Similarly, for tree DFS, we can also use stack for LCA preprocessing. But recursion depth on tree could be up to comp_cnt (e.g., if tree is a line). That's again up to 1e5, which could cause recursion stack overflow. We can implement iterative DFS for tree too. Or we can use BFS to compute depth and parent, and then fill up table. For LCA, we need parent array (up) which we can compute using BFS from root. We can do:

    queue<int> q;
    q.push(root);
    depth[root] = 0;
    up[root][0] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : tree[u]) {
            if (v == up[u][0]) continue;
            depth[v] = depth[u] + 1;
            up[v][0] = u;
            q.push(v);
        }
    }
    

    Then fill up table for all nodes using loops:

    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < comp_cnt; i++) {
            if (up[i][j-1] != -1) up[i][j] = up[up[i][j-1]][j-1];
            else up[i][j] = -1;
        }
    }
    

    This avoids recursion for tree traversal as well.

    Now the only recursion left is the bridge detection DFS. We can also implement that iteratively. But we might attempt to keep it recursive with increased stack. However, to be thorough, we can implement iterative Tarjan for bridges.

    I'll attempt to implement iterative lowlink. It's a bit more tricky but doable. We can do:

    • Use stack for DFS, with state: node, iterator index, parent_edge. We need to simulate recursion to compute low values after processing children.

    One method: Use a recursion simulation where we push (u, parent_edge) and then process its neighbors. We maintain arrays: disc, low, and also a parent array for edges. We need to process children and then after finishing children, propagate low values to parent. This can be done by using a stack that stores (u, edge_id_to_parent, start_flag). Or we can use standard two-pass: first do iterative DFS to get discovery times and parents (like a stack) but low computation requires post-order. A common approach: Perform a DFS using a stack of pairs (node, parent_edge). When we first encounter a node, we set disc and low, and push it onto a second stack (or keep a separate stack for order of processing) to later backtrack. Then after all children processed, we pop and update parent's low.

    Simpler: Use recursion and hope it's fine. Since many solutions on Codeforces for this problem (I recall it's Codeforces problem 177E? Actually, I recall a problem "Smart Beaver and merchants" maybe from Codeforces Round #... Might be problem 178B? Not sure). In any case, I can provide a solution with recursion and note that to avoid stack overflow, one can increase stack size. For the sake of completeness, I'll include a pragma to set stack size if using GCC.

    Add at top:

    #ifdef __linux__
    #include <sys/resource.h>
    #endif
    

    Then at start of main:

    #ifdef __linux__
        rlimit R;
        getrlimit(RLIMIT_STACK, &R);
        R.rlim_cur = R.rlim_max;
        setrlimit(RLIMIT_STACK, &R);
    #endif
    

    For Windows, we can use #pragma comment(linker, "/STACK:268435456"). We can include both.

    But on Codeforces, I think they use Linux, so the Linux method works. Many contestants do that. But we can also avoid recursion entirely.

    Given that we are providing a solution for the user, they likely want a reliable solution that works on large inputs. I'll implement iterative bridge detection using an explicit stack and manual management of low values.

    Let me design iterative bridge detection.

    We'll do a DFS from each unvisited node using stack.

    We need to compute disc and low for each node. The typical iterative algorithm:

    • We push a pair (u, parent_edge) onto stack, but we also need to handle exploring neighbors one by one. We can use a stack that stores a "state" with node u, a pointer to the next neighbor index, and the parent edge. Actually, we can store (u, parent_edge, iter) where iter is the current index in adjacency list. But that would be memory heavy. Alternatively, we can do the standard algorithm: Use two stacks: one for DFS order (to simulate recursion) and another for processing.

    Simpler: Use recursion for bridge detection; it's simpler and less error-prone. For safety, we can increase stack size. Let's do that.

    I'll present a solution with recursion for bridge detection and BFS for components and tree traversal. Also add stack size increase.

    But if the judge doesn't allow stack size increase, recursion may still overflow. However, many judges allow deep recursion for 1e5. I think it's fine.

    Better: implement bridge detection using iterative approach to be safe without needing to change stack limit. I'll attempt to implement iterative version.

    Idea: Perform DFS using stack of (node, parent_edge). For each node, we need to record when we first visited it, and then after exploring all children, we need to compute low from children. So we can push a marker to indicate when we finish processing a node.

    Method:

    • Use a stack st of pairs (node, state, parent_edge, child_index?). Alternatively, we can push a pair (node, parent_edge) and then after we have processed all its children we update its parent's low. But we need to know when we are done with a node.

    One common pattern: Use an extra stack order to store nodes in the order of visitation. Then, after the DFS walk (which can be done with a stack that simply pushes neighbors without tracking post-order), we compute low from children using the reverse order of visitation. Actually, the standard iterative DFS for lowlink can be done as:

    1. Perform an iterative DFS to compute disc (preorder) and record parent edge and also record the DFS order (the order in which nodes are visited). But we also need to consider back edges. However, lowlink requires updating low from children after they are processed, and also using back edges from a node to ancestors that are already visited but not necessarily its parent. This can be done if we also record for each node the list of back edges encountered.

    Alternatively, we can do the following:

    • We'll perform a classic recursive algorithm but simulate recursion with our own stack. For each frame, we need to keep the node, the parent edge id, and the current iterator index into adjacency list. We'll maintain arrays: disc, low, and an array it to store the next neighbor index for each node. We'll use a stack of (node, parent_edge). But we also need to differentiate between first-time entry and after processing children.

    We can use a method where we push a "start" and "end" markers. When we first encounter a node, we set its disc and low, and push a marker for its exit, then push its neighbors that are not visited yet. For back edges, when we encounter an already visited neighbor that is not the parent edge, we can update low of the current node immediately (since it's a back edge to an ancestor). For tree edges, we defer updating low until after child is processed.

    We need to ensure that when we process a child, after finishing it, we can update the low of the parent. So we need to know which node is the parent of the child. This can be done by storing parent information in a separate array par_edge (the edge used to reach the node). Then after processing child, we can access the parent node and update its low using the child's low. However, we need to know when a node is fully processed. We can use a stack that stores nodes in the order they are finished. When we start processing a node, we push it onto a finish_stack. After we finish all its children, we pop it and then update its parent's low.

    Algorithm:

    • Initialize arrays disc = 0, low = 0, visited? we can use disc to indicate visited.
    • Use a stack st for DFS order: each element is a node u we are about to explore. But we need to differentiate first entry. We'll use two stacks: st for nodes to process, and another finish_stack for nodes whose processing is complete. Or we can use a single stack with state flag.

    Simpler: Use recursion.

    Given time constraints, I think recursion with increased stack is acceptable.

    But let's check memory: each recursion frame might hold some variables, but depth up to 1e5, each frame maybe 32 bytes? 1e5*32 = 3.2 MB, which is okay. The default stack size for Codeforces is often 256 MB? Actually, I recall that on Codeforces, the default stack size for C++ is 256 MB? Not sure. However, some judges have default stack 8 MB. But 3.2 MB is less than 8 MB, so it might be okay even without increasing stack. Actually, recursion frame includes function arguments, return address, local variables. If we have only a few local variables, it's maybe a few dozen bytes. So 1e5 frames could be ~ a few MB. Should be safe on many judges. I've seen many solutions with DFS on trees of size 2e5 using recursion and they pass. So I'll go with recursion for bridge detection.

    Thus solution:

    C++ code:

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 100005, M = 100005;
    
    vector<pair<int, int>> adj[N];
    vector<pair<int, int>> edges;
    int disc[N], low[N];
    bool isBridge[M];
    int timer = 0;
    
    void dfs(int u, int parent_edge) {
        disc[u] = low[u] = ++timer;
        for (auto &[v, id] : adj[u]) {
            if (id == parent_edge) continue;
            if (!disc[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    isBridge[id] = true;
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }
    
    int comp[N];
    int comp_cnt = 0;
    
    void dfs_comp(int u, int cid) {
        comp[u] = cid;
        for (auto &[v, id] : adj[u]) {
            if (isBridge[id]) continue;
            if (comp[v] == -1) {
                dfs_comp(v, cid);
            }
        }
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        
        int n, m;
        cin >> n >> m;
        edges.resize(m);
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            edges[i] = {a, b};
            adj[a].push_back({b, i});
            adj[b].push_back({a, i});
        }
        
        // find bridges
        for (int i = 1; i <= n; i++) {
            if (!disc[i]) {
                dfs(i, -1);
            }
        }
        
        // assign components (2-edge-connected components)
        memset(comp, -1, sizeof(comp)); // but comp is array of size N, but we need up to n only. We'll use vector<int> comp(n+1, -1) later. Actually, better use vector.
        // I'll use vector<int> comp(n+1, -1)
    

    But we used fixed arrays; but n up to 1e5, okay. However, we need to be careful to initialize comp to -1 for indices 1..n. I'll just use vector for flexibility.

    Rewrite using vectors for scalability.

    Let's restructure:

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n+1);
    edges.resize(m);
    for (int i=0;i<m;i++) {
        int a,b; cin>>a>>b;
        edges[i]={a,b};
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    
    vector<int> disc(n+1,0), low(n+1,0);
    vector<bool> isBridge(m,false);
    int timer=0;
    
    function<void(int,int)> dfs=[&](int u, int parent_edge){
        disc[u]=low[u]=++timer;
        for(auto [v,id]:adj[u]){
            if(id==parent_edge) continue;
            if(!disc[v]){
                dfs(v,id);
                low[u]=min(low[u],low[v]);
                if(low[v]>disc[u]){
                    isBridge[id]=true;
                }
            } else {
                low[u]=min(low[u],disc[v]);
            }
        }
    };
    
    for(int i=1;i<=n;i++) if(!disc[i]) dfs(i,-1);
    

    Now component assignment:

    vector<int> comp(n+1,-1);
    int comp_cnt=0;
    function<void(int,int)> dfs_comp=[&](int u, int cid){
        comp[u]=cid;
        for(auto [v,id]:adj[u]){
            if(isBridge[id]) continue;
            if(comp[v]==-1){
                dfs_comp(v,cid);
            }
        }
    };
    for(int i=1;i<=n;i++){
        if(comp[i]==-1){
            dfs_comp(i,comp_cnt++);
        }
    }
    

    Now tree:

    vector<vector<int>> tree(comp_cnt);
    for(int i=0;i<m;i++){
        if(isBridge[i]){
            int u=edges[i].first, v=edges[i].second;
            int cu=comp[u], cv=comp[v];
            tree[cu].push_back(cv);
            tree[cv].push_back(cu);
        }
    }
    

    Now LCA prep:

    int LOG=1;
    while((1<<LOG) <= comp_cnt) LOG++;
    vector<vector<int>> up(comp_cnt, vector<int>(LOG, -1));
    vector<int> depth(comp_cnt,0);
    
    // BFS/queue to set depth and parent (up[][0])
    // find root: 0 or any.
    int root=0;
    queue<int> q;
    q.push(root);
    depth[root]=0;
    up[root][0]=-1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v:tree[u]){
            if(v==up[u][0]) continue; // parent stored as up[u][0], but for root it's -1
            // Actually, we need to know parent. Since we are BFS from root, we can set parent when first visiting.
            if(depth[v]==0 && v!=root){ // but may revisit? We'll check if depth not set.
                depth[v]=depth[u]+1;
                up[v][0]=u;
                q.push(v);
            }
        }
    }
    // For root's depth already set 0; root's parent -1.
    
    // fill up table
    for(int j=1;j<LOG;j++){
        for(int i=0;i<comp_cnt;i++){
            if(up[i][j-1]!=-1){
                up[i][j]=up[up[i][j-1]][j-1];
            } else {
                up[i][j]=-1;
            }
        }
    }
    

    But careful: In BFS, we need to avoid revisiting parent. Since we set parent as up[v][0] = u, we can check if v != parent. However, we might have already visited v via another route? Since tree is a tree, BFS will visit each node exactly once if we mark visited. We can use a visited boolean. Let's do visited array.

    vector<bool> vis(comp_cnt,false);
    q.push(root);
    vis[root]=true;
    depth[root]=0;
    up[root][0]=-1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v:tree[u]){
            if(!vis[v]){
                vis[v]=true;
                depth[v]=depth[u]+1;
                up[v][0]=u;
                q.push(v);
            }
        }
    }
    

    Now LCA function:

    auto lca=[&](int u, int v){
        if(depth[u]<depth[v]) swap(u,v);
        int diff=depth[u]-depth[v];
        for(int j=0;j<LOG;j++){
            if(diff>>j &1){
                u=up[u][j];
            }
        }
        if(u==v) return u;
        for(int j=LOG-1;j>=0;j--){
            if(up[u][j]!=up[v][j]){
                u=up[u][j];
                v=up[v][j];
            }
        }
        return up[u][0];
    };
    

    Now answer queries:

    int k; cin>>k;
    while(k--){
        int s,l; cin>>s>>l;
        int cs=comp[s], cl=comp[l];
        if(cs==cl){
            cout<<0<<"\n";
        } else {
            int lc=lca(cs,cl);
            int dist=depth[cs]+depth[cl]-2*depth[lc];
            cout<<dist<<"\n";
        }
    }
    

    Edge Cases: if comp_cnt==1, then tree has one node, up table size 1xLOG, root=0, depth[0]=0, up[0][0] = -1, etc. LCA of 0 and 0 returns? In our lca function, if cs==cl we already handled, so not called. But if they are equal, we return before lca. So no issue.

    Now test with sample.

    Potential issue: BFS visited ensures tree connectivity; since tree is connected, all nodes will be visited from root.

    Now check for correctness: Bridges detection works on undirected graph with no parallel edges. The condition low[v] > disc[u] (not >=) for bridge. Use > because for parent edge from u to child v, if low[v] == disc[u] then there is a back edge from subtree of v to u, so edge is not a bridge. If low[v] > disc[u], then no back edge to u or above, so bridge.

    Now one nuance: In iterative DFS for bridges using recursion, we treat visited neighbor as back edge and update low with disc[v] (not low[v]) because it's a back edge to an ancestor. That's correct.

    Now we need to be careful about the fact that the graph is connected, but we still have loop for unvisited nodes.

    Now complexity: O(n+m + (comp_cnt log comp_cnt) + k log comp_cnt). With n,m,k up to 1e5, fine.

    Now we should also consider that comp_cnt can be up to n (if all edges are bridges). So log up to 17. Good.

    Now about memory: edges stored as pair; adj list size 2*m; disc/low arrays size n+1; isBridge m; comp n+1; tree adjacency size comp_cnt-1 edges (at most n-1). up table size comp_cnt * LOG, with LOG ~ 17, so ~ 1.7 million ints, okay.

    Now test with some custom cases:

    Case: n=2, m=1, edge 1-2, graph is tree. Bridges: edge is bridge. Components: {1}, {2}. comp_cnt=2. Tree: 0-1. depth: root 0 depth 0, node 1 depth 1. For query (1,2): cs=0, cl=1, lca=0, dist=1. correct.

    Case: n=3, edges: 1-2,2-3,1-3 (triangle). No bridges. Components: one component containing all vertices. comp_cnt=1. Queries: any pair gives 0.

    Case: n=4, edges: 1-2,2-3,3-4,2-4. Let's compute: bridges? Edge 1-2: if removed, is 1 separated? Possibly there is path 1-2-... Actually, 1 is only connected to 2, so yes, 1-2 is bridge. Others: 2-3? There is path 2-4-3, so not bridge. 3-4? There is path 3-2-4? Actually, 3-2-4 is alternative, so not bridge. 2-4? There is path 2-3-4, so not bridge. So only bridge is 1-2. Components: {1}, {2,3,4}. Tree: edge between comps. Queries: (1,3) => 1 bridge; (2,3)=>0. Works.

    Now note: Some edges might be bridges that connect the same component? Actually, if isBridge, comp[u] != comp[v] because we skip bridges in component assignment, so they must be different. So we can assert but not needed.

    Now we need to ensure that the tree we build is indeed a tree (i.e., no cycles). Since we contracted 2-edge-connected components, the resulting graph is a tree. So we can trust.

    Now we can finalize solution.

    But I just recall: There is an alternative simpler method: just compute bridges, then for each query answer = number of bridges on the unique path between s and t in the bridge-block tree. The tree can be built as described.

    Now we might need to handle large input output efficiently: use ios::sync_with_stdio(false); cin.tie(0); cout tie? Not necessary.

    Now provide final code.

    But I must be careful about recursion depth. In some judges, they may limit recursion depth, but I'll include a stack increase just to be safe. For portability, I can include:

    static const int _ = []() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        return 0;
    }();
    

    But that doesn't increase stack.

    I can add:

    #include <sys/resource.h>
    ...
    int main() {
        rlimit R;
        getrlimit(RLIMIT_STACK, &R);
        R.rlim_cur = R.rlim_max;
        setrlimit(RLIMIT_STACK, &R);
        ...
    }
    

    For Windows, we can use pragma. I'll add a conditional.

    However, the problem likely from an online judge like Codeforces; many solutions simply use recursion without increasing stack. I think it's fine.

    But to be thorough, I'll include stack increase for Linux.

    Now final code:

    #define _GLIBCXX_DEBUG
    

    Not needed.

    Let's write the final solution.

    Edge Cases: If comp_cnt is 0? Not possible because n>=1.

    Now consider possibility that root may not be 0 if comp_cnt>0? root=0 works as long as comp_cnt>0. But if comp_cnt is 0? no.

    Now test with sample manually.

    I'll quickly simulate code in mind.

    Now let's check potential bug: In LCA, we use up[u][0] as parent. For root, up[root][0] = -1. In the BFS, we set root's up[0][0] = -1. Then when we compute up table, for j=1, we check if up[i][j-1] != -1. For root, up[root][0] = -1, so up[root][1] = -1. That's fine.

    In LCA, after lifting u to same depth, we check if u==v. Good. Then for loop, we compare up[u][j] != up[v][j]. Since up[u][j] could be -1, but if both are -1, they are equal. If one is -1 and other not, they are not equal. But when u and v are not root, eventually they will have common ancestor, and the loop will stop before hitting -1 mismatches? Actually, if they are from different branches, at some j they will have ancestors that are different; at the highest j, up[u][j] and up[v][j] will be -1 for both only after they exceed root? Let's think: For nodes that have a common ancestor, when we go too high, both become -1 (if they go beyond root). But we only loop while up[u][j] != up[v][j]; if both become -1, they are equal, so the loop would have stopped earlier when they become equal? Actually, the algorithm typical: for j from LOG-1 down to 0: if up[u][j] != up[v][j] then u=up[u][j]; v=up[v][j]. After loop, return up[u][0]. This works even if up[u][j] or up[v][j] becomes -1 as long as we only assign when they are not equal. However, if up[u][j] == -1 and up[v][j] == -1, they are equal, so condition false, no assignment. That's fine. The only potential issue is if one is -1 and the other is not, then they are not equal, we assign u = -1? But that would be invalid. Could that happen? Suppose u and v have different depths? But we lifted to same depth, so they are at same depth. Could it be that one node's ancestor at 2^j level exists (not -1) while the other's is -1? That would imply that one node's depth is less than 2^j? But if both have same depth, then if one has a 2^j-th ancestor, the other must also have a 2^j-th ancestor because depth same. Actually, if both have depth d, then if d >= 2^j, both have valid 2^j-th ancestor (maybe root). If d < 2^j, then both up[u][j] = -1 and up[v][j] = -1. So they cannot have one -1 and other not when at same depth. So safe.

    Thus LCA works.

    Now implement.

    One more subtlety: In bridge detection, we need to differentiate multiple edges? Problem says any two cities are connected by no more than one road, so no parallel edges. So fine.

    Now final code.

    We'll use vector for adjacency.

    Let's write the final code.

    We'll incorporate the stack size increase.

    I'll produce final answer now. ```cpp #include <bits/stdc++.h> using namespace std;

    // Increase stack size to avoid recursion depth issues on Linux #ifdef linux #include <sys/resource.h> #endif

    int main() { #ifdef linux rlimit R; getrlimit(RLIMIT_STACK, &R); R.rlim_cur = R.rlim_max; setrlimit(RLIMIT_STACK, &R); #endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        edges[i] = {a, b};
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }
    
    // ---------- find bridges ----------
    vector<int> disc(n + 1, 0), low(n + 1, 0);
    vector<bool> isBridge(m, false);
    int timer = 0;
    
    function<void(int, int)> dfs = [&](int u, int parent_edge) {
        disc[u] = low[u] = ++timer;
        for (auto [v, id] : adj[u]) {
            if (id == parent_edge) continue;
            if (!disc[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    isBridge[id] = true;
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    };
    
    for (int i = 1; i <= n; ++i)
        if (!disc[i])
            dfs(i, -1);
    
    // ---------- 2-edge-connected components ----------
    vector<int> comp(n + 1, -1);
    int compCnt = 0;
    
    function<void(int, int)> dfs_comp = [&](int u, int cid) {
        comp[u] = cid;
        for (auto [v, id] : adj[u]) {
            if (isBridge[id]) continue;
            if (comp[v] == -1)
                dfs_comp(v, cid);
        }
    };
    
    for (int i = 1; i <= n; ++i)
        if (comp[i] == -1)
            dfs_comp(i, compCnt++);
    
    // ---------- build bridge‑tree ----------
    vector<vector<int>> tree(compCnt);
    for (int i = 0; i < m; ++i) {
        if (isBridge[i]) {
            int u = edges[i].first, v = edges[i].second;
            int cu = comp[u], cv = comp[v];
            tree[cu].push_back(cv);
            tree[cv].push_back(cu);
        }
    }
    
    // ---------- LCA preprocessing ----------
    int LOG = 1;
    while ((1 << LOG) <= compCnt) ++LOG;
    vector<vector<int>> up(compCnt, vector<int>(LOG, -1));
    vector<int> depth(compCnt, 0);
    vector<bool> vis(compCnt, false);
    
    // BFS from root (0)
    queue<int> q;
    q.push(0);
    vis[0] = true;
    depth[0] = 0;
    up[0][0] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : tree[u]) {
            if (!vis[v]) {
                vis[v] = true;
                depth[v] = depth[u] + 1;
                up[v][0] = u;
                q.push(v);
            }
        }
    }
    
    for (int j = 1; j < LOG; ++j)
        for (int i = 0; i < compCnt; ++i)
            if (up[i][j-1] != -1)
                up[i][j] = up[ up[i][j-1] ][j-1];
    
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; ++j)
            if (diff & (1 << j))
                u = up[u][j];
        if (u == v) return u;
        for (int j = LOG-1; j >= 0; --j)
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        return up[u][0];
    };
    
    // ---------- answer queries ----------
    int k;
    cin >> k;
    while (k--) {
        int s, t;
        cin >> s >> t;
        int cs = comp[s], ct = comp[t];
        if (cs == ct) {
            cout << "0\n";
        } else {
            int l = lca(cs, ct);
            int dist = depth[cs] + depth[ct] - 2 * depth[l];
            cout << dist << "\n";
        }
    }
    
    return 0;
    

    }