#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "../debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;

	vector< vector< int > > g( n );
	vector< int > deg( n );
	for( int i = 0; i < n + 1; ++ i )
	{
		int a, b;
		cin >> a >> b;
		--a, --b;
		g[a].push_back( b );
		g[b].push_back( a );

		++deg[a], ++deg[b];
	}

	queue< int > qq;
	for( int i = 0; i < n; ++ i )
		if( deg[i] == 1 )
			qq.push( i );

	vector< int > par( n );
	iota( par.begin(), par.end(), 0 );
	vector< int > op;

	while( !qq.empty() )
	{
		const int x = qq.front();
		qq.pop();

		op.push_back( x );

		for( auto &y : g[x] )
		{
			if( par[y] == y )
			{
				par[x] = y;
				--deg[y];
				if( deg[y] == 1 )
					qq.push( y );
			}
		}
	}

	reverse( op.begin(), op.end() );
	for( auto x : op )
		par[x] = par[ par[x] ];

	vector< vector< int > > g2( n );
	for( int x = 0; x < n; ++ x )
			for( auto y : g[x] )
				if( par[x] == x && par[y] == y )
					g2[x].push_back( y );

	set< int > heads;
	for( int x = 0; x < n; ++ x )
		if( (int) g2[x].size() >= 3 )
			heads.insert( x );

	vector< vector< int > > is_cycle( 3, vector< int > ( n ) );
	vector< bool > vis( n );

	function< int( int, int, int, int ) > dfs = [&]( int x, int par, int idx, int target )
	{
		if( vis[x] ) return 0;
		vis[x] = 1;

		is_cycle[idx][x] = 0;
		if( x == target )
			return 1;

		for( auto y : g2[x] )
			if( y != par && dfs( y, x, idx, target ) )
				is_cycle[idx][x] = 1;
		
		return is_cycle[idx][x];
	};

	bool are_connected = (int) heads.size() == 2;

	if( are_connected )
	{
		const int h1 = *heads.begin();
		const int h2 = *heads.rbegin();

		int idx = 0;
		for( auto y : g2[h1] )
		{
			fill( vis.begin(), vis.end(), 0 );
			if( dfs( y, h1, idx, h2 ) )
				++idx;
		}

		if( idx < 3 )
		{
			are_connected = false;
			fill( is_cycle[0].begin(), is_cycle[0].end(), 0 );
			fill( is_cycle[1].begin(), is_cycle[1].end(), 0 );
		}
	}

	if( !are_connected )
	{
		int idx = 0;
		for( auto h : heads )
		{
			for( auto y : g2[h] )
			{
				if( is_cycle[0][y] || is_cycle[1][y] ) continue;

				fill( vis.begin(), vis.end(), 0 );
				if( dfs( y, h, idx, h ) )
					++idx;
			}
		}
	}

	//check cases
	while( q-- )
	{
		int u, v;
		cin >> u >> v;
		--u, --v;

		if( par[u] == par[v] )//same subtree
		{
			cout << 1 << '\n';
			continue;
		}
		u = par[u], v = par[v];

		if( !are_connected && (int) heads.size() == 2 )
		{
			int w = 1;
			if( is_cycle[0][u] || is_cycle[0][v] ) w *= 2;
			if( is_cycle[1][u] || is_cycle[1][v] ) w *= 2;

			cout << w << '\n';
			continue;
		}

		if( !are_connected )
		{
			if( heads.count( u ) || heads.count( v ) )
				cout << 2 << '\n';
			else
			{
				int w = 1;
				if( is_cycle[0][u] || is_cycle[0][v] ) w *= 2;
				if( is_cycle[1][u] || is_cycle[1][v] ) w *= 2;

				cout << w << '\n';
			}
			continue;
		}

		//special case

		if( heads.count( u ) || heads.count( v ) )
		{
			cout << 3 << '\n';
			continue;
		}

		int ans = 0;
		for( int idx = 0; idx < 3; ++ idx )
				if( is_cycle[idx][u] != is_cycle[idx][v] )
					ans = 1;

		ans += 3;
		cout << ans << '\n';
	}

	return 0;
}