{"problem":{"name":"Walking on a Tree","description":{"content":"Takahashi loves walking on a tree. The tree where Takahashi walks has $N$ vertices numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects Vertex $a_i$ and Vertex $b_i$. Takahashi has schedu","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc025_e"},"statements":[{"statement_type":"Markdown","content":"Takahashi loves walking on a tree. The tree where Takahashi walks has $N$ vertices numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects Vertex $a_i$ and Vertex $b_i$.\nTakahashi has scheduled $M$ walks. The $i$\\-th walk is done as follows:\n\n*   The walk involves two vertices $u_i$ and $v_i$ that are fixed beforehand.\n*   Takahashi will walk from $u_i$ to $v_i$ or from $v_i$ to $u_i$ along the shortest path.\n\nThe _happiness_ gained from the $i$\\-th walk is defined as follows:\n\n*   The happiness gained is the number of the edges traversed during the $i$\\-th walk that satisfies one of the following conditions:\n    *   In the previous walks, the edge has never been traversed.\n    *   In the previous walks, the edge has only been traversed in the direction opposite to the direction taken in the $i$\\-th walk.\n\nTakahashi would like to decide the direction of each walk so that the total happiness gained from the $M$ walks is maximized. Find the maximum total happiness that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness.\n\n## Constraints\n\n*   $1 ≤ N,M ≤ 2000$\n*   $1 ≤ a_i , b_i ≤ N$\n*   $1 ≤ u_i , v_i ≤ N$\n*   $a_i \\neq b_i$\n*   $u_i \\neq v_i$\n*   The graph given as input is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n:\n$a_{N-1}$ $b_{N-1}$\n$u_1$ $v_1$\n:\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc025_e","tags":[],"sample_group":[["4 3\n2 1\n3 1\n4 1\n2 3\n3 4\n4 2","6\n2 3\n3 4\n4 2\n\nIf we decide the directions of the walks as above, he gains the happiness of $2$ in each walk, and the total happiness will be $6$."],["5 3\n1 2\n1 3\n3 4\n3 5\n2 4\n3 5\n1 5","6\n2 4\n3 5\n5 1"],["6 4\n1 2\n2 3\n1 4\n4 5\n4 6\n2 4\n3 6\n5 6\n4 5","9\n2 4\n6 3\n5 6\n4 5"]],"created_at":"2026-03-03 11:01:14"}}