#include <vector>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
vector<vector<int>> adj ;
vector<int> heads[2], parent, depth, color, deg, q ;
using namespace std;
int main(int argc, char const *argv[]) {
   int n, nq, a, b, c=0, n3s=0, r ;
   if (scanf("%d %d", &n, &nq) != 2) abort() ;
   adj.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) ;
   }
   heads[0].resize(n,-1) ;
   heads[1].resize(n,-1) ;
   q.push_back(0) ;
   parent.resize(n, -1) ;
   depth.resize(n) ;
   depth[0] = 1 ;
   color.resize(n) ;
   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) ;
         } else if (parent[a] != b && a > b) {
            int aa = a, bb = b ;
            if (depth[aa] < depth[bb])
               swap(aa, bb) ;
            while (depth[aa] > depth[bb]) {
               heads[c][aa] = aa ;
               color[aa] |= 1<<c ;
               aa = parent[aa] ;
            }
            while (1) {
               heads[c][aa] = aa ;
               color[aa] |= 1<<c ;
               if (aa == bb)
                  break ;
               heads[c][bb] = bb ;
               color[bb] |= 1<<c ;
               aa = parent[aa] ;
               bb = parent[bb] ;
            }
            c++ ;
         }
   }
   for (int i=0; i<n; i++)
      if (color[i] == 3)
         n3s++ ;
   for (int c=0; c<2; c++) {
      q.clear() ;
      for (int i=0; i<n; i++)
         if ((color[i] >> c) & 1)
            q.push_back(i) ;
      for (int qg=0; qg<(int)q.size(); qg++)
         for (auto b: adj[q[qg]])
            if (heads[c][b] < 0 && heads[1-c][b] != b && color[b] == 0) {
               heads[c][b] = heads[c][q[qg]] ;
               q.push_back(b) ;
            }
   }
   deg.resize(n) ;
   for (int i=0; i<n; i++)
      if (color[i])
         for (auto b: adj[i])
            if (color[b] || (heads[0][b] >= 0 && heads[1][b] >= 0 &&
               heads[0][b] != heads[1][b])) {
               deg[i]++ ;
            }
   for (int i=0; i<nq; i++) {
      if (scanf("%d %d", &a, &b) != 2) abort() ;
      a-- ;
      b-- ;
      if ((heads[0][a] >= 0 && heads[0][a] == heads[0][b]) ||
          (heads[1][a] >= 0 && heads[1][a] == heads[1][b]))
         r = 1 ;
      else {
         int atyp = (heads[1][a] < 0 ? 0 : heads[0][a] < 0 ? 2 : 1) ;
         int btyp = (heads[1][b] < 0 ? 0 : heads[0][b] < 0 ? 2 : 1) ;
         if ((heads[0][a] >= 0 && deg[heads[0][a]] > 2) ||
             (heads[1][a] >= 0 && deg[heads[1][a]] > 2))
            atyp = 3 ;
         if ((heads[0][b] >= 0 && deg[heads[0][b]] > 2) ||
             (heads[1][b] >= 0 && deg[heads[1][b]] > 2))
            btyp = 3 ;
         if (n3s > 1)
            r = "3443434344333333"[atyp*4+btyp]-'0' ;
         else
            r = "2242212142222121"[atyp*4+btyp]-'0' ;
      }
      printf("%d\n", r) ;
   }
}