{"problem":{"name":"Small d and k","description":{"content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1,\\ldots,N$. For each $i=1,\\ldots,M$, the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$. Additionall","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc254_e"},"statements":[{"statement_type":"Markdown","content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1,\\ldots,N$. For each $i=1,\\ldots,M$, the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$. Additionally, **the degree of each vertex is at most $3$.**\nFor each $i=1,\\ldots,Q$, answer the following query.\n\n*   Find the sum of indices of vertices whose distances from Vertex $x_i$ are at most $k_i$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 1.5 \\times 10^5$\n*   $0 \\leq M \\leq \\min (\\frac{N(N-1)}{2},\\frac{3N}{2})$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   $(a_i,b_i) \\neq (a_j,b_j)$, if $i\\neq j$.\n*   The degree of each vertex in the graph is at most $3$.\n*   $1 \\leq Q \\leq 1.5 \\times 10^5$\n*   $1 \\leq x_i \\leq N$\n*   $0 \\leq k_i \\leq 3$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n$Q$\n$x_1$ $k_1$\n$\\vdots$\n$x_Q$ $k_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc254_e","tags":[],"sample_group":[["6 5\n2 3\n3 4\n3 5\n5 6\n2 6\n7\n1 1\n2 2\n2 0\n2 3\n4 1\n6 0\n4 3","1\n20\n2\n20\n7\n6\n20\n\nFor the $1$\\-st query, the only vertex whose distance from Vertex $1$ is at most $1$ is Vertex $1$, so the answer is $1$.  \nFor the $2$\\-nd query, the vertices whose distances from Vertex $2$ are at most $2$ are Vertex $2$, $3$, $4$, $5$, and $6$, so the answer is their sum, $20$.  \nThe $3$\\-rd and subsequent queries can be answered similarly."]],"created_at":"2026-03-03 11:01:14"}}