{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003ezxa have an unrooted tree with $n$ nodes, including $(n-1)$ undirected edges, whose nodes are numbered from $1$ to $n$. The degree of each node is defined as the number of the edges connected to it, and each node whose degree is $1$ is defined as the leaf node of the tree.\u003cbr\u003e\u003cbr\u003ezxa wanna set each node\u0027s beautiful level, which must be a positive integer. His unrooted tree has $m(1\\leq m\\leq n)$ leaf nodes, $k(1\\leq k\\leq m)$ leaf nodes of which have already been setted their beautiful levels, so that zxa only needs to set the other nodes\u0027 beautiful levels.\u003cbr\u003e\u003cbr\u003ezxa is interested to know, assuming that the ugly level of each edge is defined as the absolute difference of the beautiful levels between two nodes connected by this edge, and the ugly level of the tree is the maximum of the ugly levels of **all the edges on this tree**, then what is the minimum possible ugly level of the tree, can you help him?\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an positive integer $T$, represents there are $T$ test cases.\u003cbr\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains two positive integers $n$ and $k$, represent the tree has $n$ nodes, $k$ leaf nodes of which have already been setted their beautiful levels.\u003cbr\u003e\u003cbr\u003eThe next $(n-1)$ lines, each line contains two distinct positive integers $u$ and $v$, repersent there is an undirected edge between node $u$ and node $v$.\u003cbr\u003e\u003cbr\u003eThe next $k$ lines, each lines contains two positive integers $u$ and $w$, repersent node $u$ is a leaf node, whose beautiful level is $w$.\u003cbr\u003e\u003cbr\u003eThere is a blank between each integer with no other extra space in one line.\u003cbr\u003e\u003cbr\u003eIt\u0027s guaranteed that the input edges constitute a tree.\u003cbr\u003e\u003cbr\u003e$1\\leq T\\leq 10,2\\leq n\\leq 5\\cdot10^4,1\\leq k\\leq n,1\\leq u,v\\leq n,1\\leq w\\leq 10^9$\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output in one line a non-negative integer, repersents the minimum possible ugly level of the tree.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 2\r\n1 2\r\n1 3\r\n2 4\r\n3 9\r\n6 2\r\n1 2\r\n1 3\r\n1 4\r\n2 5\r\n2 6\r\n3 6\r\n5 9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIf you need a larger stack size, please use #pragma comment(linker, \"/STACK:102400000,102400000\") and submit your solution using C++.\u003cbr\u003e"}}]}