#include <vector>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
vector<vector<int>> adj, adj2 ;
vector<int> parent, depth, q, deg, head, spec, path, cache ;
vector<pair<int, int>> remap ;
using namespace std;
void dfs(int a, int h) {
   if (head[a] < 0) {
      head[a] = h ;
      for (auto b: adj[a])
         if (deg[b] == 0)
            dfs(b, h) ;
   }
}
int dfs(int a, int b, unsigned long long used) {
   if (a == b)
      return 1 ;
   int r = 0 ;
   for (auto c: adj2[a])
      if (((used >> c) & 1) == 0)
         r += dfs(c, b, used | (1LL<<a)) ;
   return r ;
}
int main(int argc, char const *argv[]) {
   int n, nq, a, b, r ;
   if (scanf("%d %d", &n, &nq) != 2) abort() ;
   adj.resize(n) ;
   deg.resize(n) ;
   for (int i=0; i<n+1; i++) {
      if (scanf("%d %d", &a, &b) != 2) abort() ;
      adj[a-1].push_back(b-1) ;
      adj[b-1].push_back(a-1) ;
      deg[a-1]++ ;
      deg[b-1]++ ;
   }
   q.push_back(0) ;
   parent.resize(n, -1) ;
   depth.resize(n) ;
   depth[0] = 1 ;
   for (int qg=0; qg<(int)q.size(); qg++) {
      a = q[qg] ;
      for (auto b: adj[a])
         if (depth[b] == 0) {
            parent[b] = a ;
            depth[b] = depth[a] + 1 ;
            q.push_back(b) ;
         }
   }
   for (int i=0; i<n; i++)
      if (deg[i] == 1) {
         for (int a=i; a >= 0; ) {
            deg[a]-- ;
            int nexta = -1 ;
            for (int b: adj[a])
               if (deg[b] > 0) {
                  deg[b]-- ;
                  if (deg[b] == 1) {
                     nexta = b ;
                     break ;
                  }
               }
            a = nexta ;
         }
      }
   head.resize(n, -1) ;
   for (int i=0; i<n; i++)
      if (deg[i] > 0)
         dfs(i, i) ;
   remap.resize(n) ;
   for (int i=0; i<n; i++)
      if (deg[i] > 2) {
         remap[i] = {(int)spec.size(), (int)spec.size()} ;
         spec.push_back(i) ;
      }
   int newn = spec.size() ;
   for (auto a: spec)
      for (auto b: adj[a])
         if (deg[b] > 0) {
            path = {a} ;
            while (deg[b] == 2) {
               path.push_back(b) ;
               int newb = -1 ;
               for (auto c: adj[b])
                  if (deg[c] > 0 && c != path[path.size()-2]) {
                     newb = c ;
                     break ;
                  }
               b = newb ;
            }
            path.push_back(b) ;
            if (path[0] > path[path.size()-1] ||
                (path[0] == path[path.size()-1] &&
                  (path.size() == 2 || path[1] > path[path.size()-2]))) {
               adj2.resize(newn+2) ;
               adj2[remap[a].first].push_back(newn) ;
               adj2[newn].push_back(newn+1) ;
               adj2[newn+1].push_back(remap[b].first) ;
               adj2[newn].push_back(remap[a].first) ;
               adj2[newn+1].push_back(newn) ;
               adj2[remap[b].first].push_back(newn+1) ;
               for (int j=1; j+1<(int)path.size(); j++)
                  remap[path[j]] = {newn, newn+1} ;
               newn += 2 ;
            }
         }
   int cachesize = newn * newn ;
   cache.resize(cachesize, -1) ;
   for (int i=0; i<nq; i++) {
      if (scanf("%d %d", &a, &b) != 2) abort() ;
      a = head[a-1] ;
      b = head[b-1] ;
      if (a == b)
         r = 1 ;
      else {
         a = remap[a].first ;
         b = remap[b].second ;
         if (a < b)
            swap(a, b) ;
         int k = a * newn + b ;
         if (cache[k] >= 0)
            r = cache[k] ;
         else {
            r = dfs(a, b, 1<<a) ;
            cache[k] = r ;
         }
      }
      cout << r << endl ;
   }
}