{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Hindi](https://www.codechef.com/download/translated/LTIME84/hindi/TREDIFF.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME84/bengali/TREDIFF.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/LTIME84/mandarin/TREDIFF.pdf), [Russian](https://www.codechef.com/download/translated/LTIME84/russian/TREDIFF.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME84/vietnamese/TREDIFF.pdf) as well.\r\n\r\nYou are given a tree with $N$ nodes (numbered $1$ through $N$). For each valid $i$, node $i$ has a value $A_i$.\r\n\r\nYou should answer $Q$ queries. In each query:\r\n- You are given two nodes $a$ and $b$.\r\n- Let $S$ denote the set of all nodes on the simple path between the nodes $a$ and $b$ (including these nodes).\r\n- Find the minimum value of $|A_x-A_y|$ over all pairs $x, y \\in S$ such that $x \\neq y$.\r\n\r\n### Input\r\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\r\n- The first line of each test case contains two space-separated integers $N$ and $Q$.\r\n- The second line contains $N$ space-separated integers $A_1, A_2, \\ldots, A_N$.\r\n- Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.\r\n- Each of the last $Q$ lines contains two space-separated integers $a$ and $b$ describing a query.\r\n\r\n### Output\r\nFor each query, print a single line containing one integer ― the answer to the query.\r\n\r\n### Constraints\r\n- $1 \\le T \\le 20$\r\n- $2 \\le N \\le 2 \\cdot 10^5$\r\n- $1 \\le Q \\le 2 \\cdot 10^5$\r\n- $1 \\le A_i \\le 100$ for each valid $i$\r\n- $1 \\le u, v, a, b \\le N$\r\n- $a \\neq b$\r\n- the sum of $N$ over all test cases does not exceed $5 \\cdot 10^5$\r\n- the sum of $Q$ over all test cases does not exceed $5 \\cdot 10^5$\r\n\r\n### Subtasks\r\n**Subtask #1 (30 points):** $N, Q \\le 1,000$\r\n\r\n**Subtask #2 (70 points):** original constraints"}},{"title":"Sample 1","value":{"format":"MD","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\u003e1\r\n6 3\r\n10 2 5 6 5 6\r\n1 2\r\n2 3\r\n2 4\r\n1 5\r\n5 6\r\n5 6\r\n3 5\r\n1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n0\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n**Example case 1:**\r\n- For the first query, $S\u003d\\{5, 6\\}$, so the answer is $|A_5-A_6|\u003d1$.\r\n- For the second query, $S\u003d\\{3, 2, 1, 5\\}$ and we can see that $|A_3-A_5|\u003d0$.\r\n- For the third query, $S\u003d\\{1, 2, 4\\}$."}}]}