#include<bits/stdc++.h>

                                                        using namespace std;

                                                         #define FOR(i,a,b) for(int i = (a); i < (b); i++)
                                                         #define RFOR(i,a,b) for(int i = (a) - 1; i>=(b);i--)
                                                         #define rep(i,n) FOR(i,0,n)
                                                         #define PB push_back
                                                         #define SZ(a) (int)a.size()
                                                         #define ALL(a) a.begin(), a.end()
                                                         #define FILL(a, value) memset(a, value, sizeof(a))
                                                         #define IOS ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0);
                                                         #define f first
                                                         #define s second


                                                        typedef   long long LL ;
                                                        typedef  vector<int > VI ;
                                                        typedef vector<LL > VL;
                                                        typedef pair<int,int > PII;
                                                        typedef pair<LL,LL> PLL;

                                                        const LL LINF = (LL)1e18 +47;
                                                        const int INF =  (int)1e9 + 47 ;
                                                        const int MOD = (int)1e9 + 7;
                                                        const int modulo =998244353;
                                                        const int nax =     (int)1e5 + 100;
                                                        const double EPS = 1e-10;
                                                        const int K=26;
                                                        const double PI  = acos(-1.0);
                                                        clock_t  time_start = clock();


                                                        int clr[nax];
                                                        vector<int > g[nax];
                                                        set<int> s[nax];
                                                        int ans = 0;

                                                        void merge(int v ,int p )
                                                        {

                                                           VI vec;
                                                           FOR(i,0,SZ(g[v]))
                                                           {
                                                            if(g[v][i] == p)continue;
                                                            vec.PB(i);
                                                           }
                                                           vector<vector<int >>vv(4,VI(SZ(g[v]),0));
                                                           vector<vector<int>>can(SZ(g[v]),VI(SZ(g[v]),-1));
                                                           FOR(i,0,SZ(vec))
                                                           {
                                                             FOR(j,0,SZ(vec))
                                                             {
                                                               if(i == j)continue;
                                                               for(auto it :s[g[v][vec[i]]])
                                                               {
                                                                 if(s[g[v][vec[j]]].count(it))
                                                                 {
                                                                  can[vec[i]][vec[j]] = 1;
                                                                  break;
                                                                 }
                                                               }
                                                             }
                                                           }
                                                           int bst = 0;
                                                           do
                                                           {
                                                             int res = 0;
                                                              VI ar;
                                                             for(int i = 0; i < SZ(vec) -1;i +=2)
                                                             {
                                                               if(can[vec[i]][vec[i + 1]] ==-1)
                                                               {
                                                                ar.PB(vec[i]);
                                                                ar.PB(vec[i + 1]);
                                                               }
                                                               else res++;
                                                             }
                                                             if(SZ(vec)% 2!=0)ar.PB(vec.back());
                                                             bst = max(bst,res);
                                                             for(auto x : ar)vv[res][x] = 1;
                                                           }while(next_permutation(ALL(vec)));
                                                           vec.clear();
                                                           FOR(j,0,SZ(g[v]))
                                                           {
                                                             if(vv[bst][j] !=0)vec.PB(j);
                                                           }
                                                           ans+=bst ;

                                                           int mx = 0,id =-1;
                                                           for(auto x : vec)
                                                           {
                                                             if(SZ(s[g[v][x]]) > mx)
                                                             {
                                                              mx = SZ(s[g[v][x]]);
                                                              id = x;
                                                             }
                                                           }
                                                           int idd = id == -1 ? -1 : g[v][id];
                                                           for(auto x : vec)
                                                           {
                                                            if(x == id)continue;
                                                            for(auto it : s[g[v][x]])s[idd].insert(it);
                                                           }
                                                           if(id!=-1)s[v].swap(s[idd]);
                                                        }
                                                        void dfs(int v,int p =-1)
                                                        {
                                                          if(clr[v])
                                                          {
                                                            s[v].insert(clr[v]);
                                                            return ;
                                                          }
                                                          for(auto to : g[v])
                                                          {
                                                            if(to == p)continue;
                                                            dfs(to,v);
                                                          }
                                                          merge(v,p);

                                                        }
                                                        int main(){
                                                          IOS;

                                                          int n,l;
                                                          cin >> n >> l;
                                                          rep(i,n - 1)
                                                          {
                                                             int a,b;
                                                             cin >> a >> b;
                                                             --a,--b;
                                                             g[a].PB(b);
                                                             g[b].PB(a);
                                                          }
                                                          rep(i,l)
                                                          {
                                                             int a,color;
                                                             cin >> a >> color;
                                                             --a;
                                                             clr[a] = color;
                                                          }
                                                          if(n == 1)
                                                          {
                                                            cout << 0 ;
                                                            return 0;
                                                          }
                                                          if(n == 2)
                                                          {
                                                            if(clr[0] == clr[1])cout << 1 ;
                                                            else cout << 0 ;
                                                            return  0;
                                                          }
                                                          FOR(i,0,n)
                                                          {
                                                            if(!clr[i])
                                                            {
                                                              dfs(i);
                                                              cout << ans << '\n';
                                                              return 0;
                                                            }
                                                          }


                                                        }