

Paths on the treeTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2818 Accepted Submission(s): 880 Problem Description bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n. There are m paths on the tree. bobo would like to pick some paths while any two paths do not share common vertices. Find the maximum number of paths bobo can pick. Input The input consists of several tests. For each tests: The first line contains n,m (1≤n,m≤10^{5}). Each of the following (n  1) lines contain 2 integers a_{i},b_{i} denoting an edge between vertices a_{i} and b_{i} (1≤a_{i},b_{i}≤n). Each of the following m lines contain 2 integers u_{i},v_{i} denoting a path between vertices u_{i} and v_{i} (1≤u_{i},v_{i}≤n). Output For each tests: A single integer, the maximum number of paths. Sample Input
Sample Output
Author Xiaoxu Guo (ftiasch) Source  
