#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define CERR( ANSWER ) cerr << ANSWER << "\n";
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define CERR( ANSWER ) 
#endif
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT

template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; }

#define POWER( ANSWER , ARGUMENT , EXPONENT )				\
  static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT );	\
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;			\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;	\
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\

#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO )		\
  ll ANSWER{ 1 };							\
  {									\
    ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\

#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_I , LENGTH , MODULO ) \
  static ll ANSWER[LENGTH];						\
  static ll ANSWER_INV[LENGTH];						\
  static ll INVERSE[LENGTH];						\
  {									\
    ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1;				\
    ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL;			\
    FOREQ( i , 1 , MAX_I ){						\
      ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
    }									\
    ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
    FOREQ( i , 2 , MAX_I ){						\
      ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO; \
    }									\
  }									\

// 通常の二分探索その１
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION >= TARGETを満たす最小の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER;								\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
    ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
    while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
      CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
    CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << ">=0" ); \
  }									\

// 通常の二分探索その２
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER;								\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
    ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
    while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
      CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
    CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "<=0" ); \
  }									\

// 通常の二分探索その３
// EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION >= TARGETを満たす最大の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER;								\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
    ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
    while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
      CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
    CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << ">=0" ); \
  }									\

// 通常の二分探索その４
// EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION <= TARGETを満たす最小の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER;								\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
    ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
    while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
      CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
    CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "<=0" ); \
  }									\



// 二進法の二分探索
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。
#define BBS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  ll ANSWER = MINIMUM;							\
  {									\
    ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH = 1;			\
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH *= 2;			\
    }									\
    VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2;				\
    ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER;			\
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH != 0 ){			\
      ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH; \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER;			\
	break;								\
      } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){	\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER;			\
      }									\
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2;			\
    }									\
    ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH;			\
  }									\

// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&

inline CEXPR( int , bound_NQ , 200000 );
list<int> edge[bound_NQ] = {};
inline list<int> E( const int& i ) { return edge[i]; }

// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH )				\
  template <int V_max,list<int> E(const int&)>				\
  class BREADTH ## FirstSearch						\
  {									\
									\
  private:								\
    int m_V;								\
    int m_init;								\
    list<int> m_next;							\
    bool m_found[V_max];						\
    int m_prev[V_max];							\
									\
  public:								\
    inline BREADTH ## FirstSearch( const int& V );			\
    inline BREADTH ## FirstSearch( const int& V , const int& init );	\
									\
    inline void Reset( const int& init );				\
    inline void Shift( const int& init );				\
									\
    inline const int& size() const;					\
    inline const int& init() const;					\
    inline bool& found( const int& i );					\
    inline const int& prev( const int& i ) const;			\
									\
    int Next();								\
									\
  };									\

#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH )			\
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V , const int& init ) : BREADTH ## FirstSearch( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
									\
  template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \
  template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \
									\
  template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::size() const { return m_V; } \
  template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::init() const { return m_init; } \
  template <int V_max,list<int> E(const int&)> inline bool& BREADTH ## FirstSearch<V_max,E>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
  template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
									\
  template <int V_max,list<int> E(const int&)>				\
  int BREADTH ## FirstSearch<V_max,E>::Next()				\
  {									\
									\
    if( m_next.empty() ){						\
									\
      return -1;							\
									\
    }									\
									\
    const int i_curr = m_next.front();					\
    m_next.pop_front();							\
    list<int> edge = E( i_curr );					\
									\
    while( ! edge.empty() ){						\
									\
      const int& i = edge.front();					\
      bool& found_i = found( i );					\
									\
      if( ! found_i ){							\
									\
	m_next.PUSH( i );						\
	m_prev[i] = i_curr;						\
	found_i = true;							\
									\
      }									\
									\
      edge.pop_front();							\
									\
    }									\
									\
    return i_curr;							\
									\
  }									\

DECLARATION_OF_FIRST_SEARCH( Depth );

DEFINITION_OF_FIRST_SEARCH( Depth , push_front );

template <int V_max,list<int> E(const int&),int digit = 0>
class DepthFirstSearchOnTree :
  public DepthFirstSearch<V_max,E>
{

private:
  // メモリが厳しい場合、以下で不要なものを消す。
  int m_reversed[V_max];

  list<int> m_children[V_max];
  bool m_set_children;

  int m_depth[V_max];

  int m_height[V_max];
  bool m_set_height;

  int m_weight[V_max];
  bool m_set_weight;

  int m_doubling[digit][V_max];
  bool m_set_doubling;

public:
  inline DepthFirstSearchOnTree( const int& V , const int& root );
  inline void Reset( const int& init ) = delete;
  inline void Shift( const int& init ) = delete;

  inline const int& Root() const;
  inline const int& Parent( const int& i ) const;
  inline const list<int>& Children( const int& i );
  inline const int& Depth( const int& i ) const;
  inline const int& Height( const int& i );
  inline const int& Weight( const int& i );

  // 各ノードの高さ < 2^digitの時のみサポート。
  int Ancestor( int i , int n );
  int LCA( int i , int j );
  int LCA( int i , int j , int& i_prev , int& j_prev );
  
private:
  void SetChildren();
  void SetHeight();
  void SetWeight();

  // 各ノードの高さ < 2^digitの時のみサポート。
  // LCA()を呼ぶ前にAncestor()経由で完全にダブリングを設定するため、
  // 遅延評価する../../../../Mathematics/Function/Iteration/Doubling/のダブリングで代用しない。
  void SetDoubling();

};

template <int V_max,list<int> E(const int&),int digit> inline DepthFirstSearchOnTree<V_max,E,digit>::DepthFirstSearchOnTree( const int& V , const int& root ) :
  DepthFirstSearch<V_max,E>( V , root ) , m_reversed() , m_children() , m_set_children() , m_depth() , m_height() , m_set_height() , m_weight() , m_set_weight() , m_doubling() , m_set_doubling()
{

  int n = DepthFirstSearch<V_max,E>::size();
  
  while( --n >= 0 ){
    
    const int& i = m_reversed[n] = DepthFirstSearch<V_max,E>::Next();
    const int& j = Parent( i );

    if( j != -1 ){

      m_depth[i] = m_depth[j] + 1;

    }

  }

}

template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Root() const { return DepthFirstSearch<V_max,E>::init(); }

template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Parent( const int& i ) const { return DepthFirstSearch<V_max,E>::prev( i ); }
template <int V_max,list<int> E(const int&),int digit> inline const list<int>& DepthFirstSearchOnTree<V_max,E,digit>::Children( const int& i ) { if( ! m_set_children ){ SetChildren(); } return m_children[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Depth( const int& i ) const { return m_depth[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Height( const int& i ) { if( ! m_set_height ){ SetHeight(); } return m_height[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Weight( const int& i ) { if( ! m_set_weight ){ SetWeight(); } return m_weight[i]; }

template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::Ancestor( int i , int n )
{

  if( ! m_set_doubling ){

    SetDoubling();

  }

  assert( ( n >> digit ) == 0 );
    
  int d = 0;
  
  while( n != 0 ){

    if( ( n & 1 ) == 1 ){

      assert( ( i = m_doubling[d][i] ) != -1 );

    }
    
    d++;
    n >>= 1;

  }

  return i;

}

template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j )
{

  int diff = Depth( i ) - Depth( j );

  if( diff < 0 ){

    swap( i , j );
    diff *= -1;

  }
    
  i = Ancestor( i , diff );

  if( i == j ){

    return i;
      
  }
    
  int d = digit;

  while( --d >= 0 ){

    const int ( &doubling_d )[V_max] = m_doubling[d];
    const int& doubling_d_i = doubling_d[i];
    const int& doubling_d_j = doubling_d[j];

    if( doubling_d_i != doubling_d_j ){

      i = doubling_d_i;
      j = doubling_d_j;
      assert( i != -1 );
      assert( j != -1 );

    }

  }

  return Parent( i );

}

template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j , int& i_prev , int& j_prev )
{

  if( i == j ){

    i_prev = j_prev = -1;
    return i;

  }
  
  int diff = Depth( i ) - Depth( j );

  if( diff < 0 ){

    return LCA( j , i , j_prev , i_prev );

  }
  
  if( diff > 0 ){

    i_prev = Ancestor( i , diff - 1 );
    i = Parent( i_prev );
    assert( i != -1 );
    
    if( i == j ){

      j_prev = -1;
      return i;
      
    }
    
  } else if( ! m_set_doubling ){

    SetDoubling();

  }
    
  int d = digit;

  while( --d >= 0 ){

    const int ( &doubling_d )[V_max] = m_doubling[d];
    const int& doubling_d_i = doubling_d[i];
    const int& doubling_d_j = doubling_d[j];

    if( doubling_d_i != doubling_d_j ){

      i = doubling_d_i;
      j = doubling_d_j;
      assert( i != -1 );
      assert( j != -1 );

    }

  }

  i_prev = i;
  j_prev = j;
  return Parent( i_prev );

}

template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetChildren()
{

  assert( !m_set_children );
  m_set_children = true;
  const int& V = DepthFirstSearch<V_max,E>::size();
  
  for( int i = 0 ; i < V ; i++ ){

    const int& parent_i = Parent( i );

    if( parent_i != -1 ){

      m_children[parent_i].push_back( i );

    }

  }

  return;
  
}

template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetHeight()
{

  assert( !m_set_height );
  m_set_height = true;
  const int& V = DepthFirstSearch<V_max,E>::size();
  
  for( int i = 0 ; i < V ; i++ ){

    const int& reversed_i = m_reversed[i];
    const int& parent_i = Parent( reversed_i );

    if( parent_i != -1 ){

      int& height_parent_i = m_height[parent_i];
      const int& height_i = m_height[reversed_i];
      height_parent_i > height_i ? height_parent_i : height_parent_i = height_i + 1;

    }

  }

  return;

}

template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetWeight()
{

  assert( !m_set_weight );
  m_set_weight = true;
  const int& V = DepthFirstSearch<V_max,E>::size();
  
  for( int i = 0 ; i < V ; i++ ){

    const int& reversed_i = m_reversed[i];
    const int& parent_i = Parent( reversed_i );

    if( parent_i != -1 ){

      m_weight[parent_i] += m_weight[reversed_i] + 1;

    }

  }

  return;

}

template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetDoubling()
{

  assert( !m_set_doubling );
  m_set_doubling = true;
  const int& V = DepthFirstSearch<V_max,E>::size();
  
  {
    
    int ( &doubling_0 )[V_max] = m_doubling[0];
    const int& r = Root();

    for( int i = 0 ; i < V ; i++ ){

      doubling_0[i] = Parent( i );

    }

  }
  
  for( int d = 1 ; d < digit ; d++ ){

    int ( &doubling_d )[V_max] = m_doubling[d];
    int ( &doubling_d_minus )[V_max] = m_doubling[d-1];

    for( int i = 0 ; i < V ; i++ ){

      const int& doubling_d_minus_i = doubling_d_minus[i];
      doubling_d[i] = doubling_d_minus_i == -1 ? -1 : doubling_d_minus[doubling_d_minus_i];

    }

  }

  return;

}

int main()
{
  UNTIE;
  CIN_ASSERT( N , 2 , bound_NQ );
  CIN_ASSERT( Q , 1 , bound_NQ );
  int N_minus = N - 1;
  REPEAT( N_minus ){
    CIN_ASSERT( A , 1 , N );
    CIN_ASSERT( B , 1 , N );
    A--;
    B--;
    edge[A].push_back( B );
    edge[B].push_back( A );
  }
  static DepthFirstSearchOnTree<bound_NQ,E,18> dfs{ N , 0 };
  REPEAT( Q ){
    CIN_ASSERT( S , 1 , N );
    CIN_ASSERT( T , 1 , N );
    S--;
    T--;
    int depth_S = dfs.Depth( S );
    int depth_T = dfs.Depth( T );
    int diff = depth_S - depth_T;
    if( diff < 0 ){
      swap( S , T );
      swap( depth_S , depth_T );
      diff *= -1;
    }
    if( S == T ){
      COUT( N );
    } else if( diff % 2 == 1 ){
      COUT( 0 );
    } else if( diff == 0 ){
      int S_prev;
      int T_prev;
      dfs.LCA( S , T , S_prev , T_prev );
      COUT( N - dfs.Weight( S_prev ) - dfs.Weight( T_prev ) - 2 );
    } else {
      int LCA = dfs.LCA( S , T );
      int centre_prev = dfs.Ancestor( S , depth_S - 1 - dfs.Depth( LCA ) - diff / 2 );
      const int& centre = dfs.Parent( centre_prev );
      COUT( dfs.Weight( centre ) - dfs.Weight( centre_prev ) );
    }
  }
  QUIT;
}