#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9;
const int T = 18;
struct Tree {
  vector<int> a;
  int size;
  Tree() {}
  void init(vector<int>& data) {
    size = data.size();
    a.clear();
    a.resize(size * 4);
    init2(0, 0, size, data);
  }
  void init2(int v, int ll, int rr, vector<int>& data) {
    if (ll + 1 == rr) {
      a[v] = data[ll];
      return;
    }
    init2(v * 2 + 1, ll, (ll + rr) / 2, data);
    init2(v * 2 + 2, (ll + rr) / 2, rr, data);
    a[v] = max(a[v * 2 + 1], a[v * 2 + 2] + (ll + rr) / 2 - ll);
  }
  int getMax(int l, int r) { return getMaxSeg(0, 0, size, l, r); }
  int getMaxSeg(int v, int ll, int rr, int l, int r) {
    if (ll >= r || l >= rr) return -inf;
    if (l <= ll && rr <= r) return a[v];
    int r1, r2;
    r1 = getMaxSeg(v * 2 + 1, ll, (ll + rr) / 2, l, r);
    r2 = getMaxSeg(v * 2 + 2, (ll + rr) / 2, rr, l, r);
    if (l < (ll + rr) / 2) {
      r2 += (ll + rr) / 2 - max(l, ll);
    }
    return max(r1, r2);
  }
};
vector<int> e[maxn];
int par0[maxn];
int distToPath[maxn];
int jump[maxn][T];
int tin[maxn];
int tout[maxn];
int H[maxn];
int goToRoad[maxn];
int idOnPath[maxn];
int firstChild[maxn];
pair<int, int> depth1[maxn];
pair<int, int> depth2[maxn];
vector<pair<int, int> > query;
vector<pair<int, int> > edges;
int longestPathInTree[maxn];
bool use[maxn];
bool onLongestPath[maxn];
pair<int, int> longestPath;
vector<int> path;
vector<int> data;
Tree leftttt;
Tree rightt;
int topPath = -1;
int ans;
int tmr;
int n, m;
pair<int, int> dfsLongestPath(int v) {
  pair<int, int> prT, pr1, pr2;
  pr1 = make_pair(0, v);
  pr2 = make_pair(0, v);
  use[v] = 1;
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (!use[e[v][i]]) {
      prT = dfsLongestPath(e[v][i]);
      par0[e[v][i]] = v;
      if (pr2.first < prT.first) swap(prT, pr2);
      if (pr1.first < pr2.first) swap(pr1, pr2);
    }
  }
  if (pr1.first + pr2.first > ans) {
    longestPath = make_pair(pr1.second, pr2.second);
    topPath = v;
    ans = pr1.first + pr2.first;
  }
  return make_pair(pr1.first + 1, pr1.second);
}
pair<int, int> dfs1(int v, int h, int p, int ch) {
  int newCh;
  pair<int, int> tmp;
  use[v] = 1;
  distToPath[v] = h;
  depth1[v] = depth2[v] = make_pair(0, v);
  goToRoad[v] = p;
  firstChild[v] = ch;
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (onLongestPath[e[v][i]]) continue;
    if (!use[e[v][i]]) {
      newCh = (ch == -1) ? e[v][i] : ch;
      tmp = dfs1(e[v][i], h + 1, p, newCh);
      if (tmp.first > depth2[v].first) swap(tmp, depth2[v]);
      if (depth2[v].first > depth1[v].first) swap(depth1[v], depth2[v]);
    }
  }
  return make_pair(depth1[v].first + 1, v);
}
void dfs2(int v, int wayUp) {
  int newWayUp;
  use[v] = 1;
  longestPathInTree[v] = max(depth1[v].first, wayUp);
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (onLongestPath[e[v][i]]) continue;
    if (!use[e[v][i]]) {
      if (depth1[v].second == e[v][i])
        newWayUp = max(wayUp, depth2[v].first);
      else
        newWayUp = max(wayUp, depth1[v].first);
      dfs2(e[v][i], newWayUp + 1);
    }
  }
}
void dfs3(int v, int p, int id) {
  use[v] = 1;
  if (id == 0)
    jump[v][id] = p;
  else
    jump[v][id] = jump[jump[v][id - 1]][id - 1];
  for (int i = 0; i < (int)e[v].size(); i++)
    if (!use[e[v][i]]) dfs3(e[v][i], v, id);
}
void dfs4(int v, int h) {
  tin[v] = tmr++;
  H[v] = h;
  use[v] = 1;
  for (int i = 0; i < (int)e[v].size(); i++)
    if (!use[e[v][i]]) dfs4(e[v][i], h + 1);
  tout[v] = tmr++;
}
bool checkPar(int v, int u) { return tin[v] <= tin[u] && tout[u] <= tout[v]; }
int getLCA(int v, int u) {
  if (checkPar(v, u)) return v;
  if (checkPar(u, v)) return u;
  for (int i = T - 1; i >= 0; i--)
    if (!checkPar(jump[v][i], u)) v = jump[v][i];
  return jump[v][0];
}
int getUp(int v, int k) {
  for (int i = T - 1; i >= 0; i--)
    if ((1 << i) <= k) {
      v = jump[v][i];
      k -= (1 << i);
    }
  return v;
}
int calc(int l, int r, int v) {
  int idv;
  int n = path.size();
  idv = idOnPath[goToRoad[v]];
  int ans = 0;
  ans = longestPathInTree[v];
  if ((idv + 1) < (r) + 1)
    ans = max(ans, leftttt.getMax((idv + 1), (r) + 1) + 1 + distToPath[v]);
  pair<int, int> pr = make_pair(l, idv - 1);
  pr = make_pair(n - pr.first - 1, n - pr.second - 1);
  pr = make_pair(pr.second, pr.first);
  if (pr.first < pr.second + 1)
    ans = max(ans, rightt.getMax(pr.first, pr.second + 1) + 1 + distToPath[v]);
  return ans;
}
vector<int> solve() {
  int v, u;
  path.clear();
  for (int i = 0; i < n; i++) e[i].clear();
  for (int i = 0; i < (int)edges.size(); i++) {
    v = edges[i].first;
    u = edges[i].second;
    v--;
    u--;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  memset(use, 0, sizeof(use));
  topPath = -1;
  ans = 0;
  dfsLongestPath(0);
  assert(topPath != -1);
  memset(onLongestPath, 0, sizeof(onLongestPath));
  for (; longestPath.first != topPath;
       longestPath.first = par0[longestPath.first]) {
    onLongestPath[longestPath.first] = 1;
    path.push_back(longestPath.first);
  }
  vector<int> path1;
  for (; longestPath.second != topPath;
       longestPath.second = par0[longestPath.second]) {
    onLongestPath[longestPath.second] = 1;
    path1.push_back(longestPath.second);
  }
  path.push_back(topPath);
  onLongestPath[topPath] = 1;
  reverse(path1.begin(), path1.end());
  for (int i = 0; i < (int)path1.size(); i++) path.push_back(path1[i]);
  memset(use, 0, sizeof(use));
  memset(firstChild, 0, sizeof(firstChild));
  for (int i = 0; i < (int)path.size(); i++) dfs1(path[i], 0, path[i], -1);
  memset(use, 0, sizeof(use));
  for (int i = 0; i < (int)path.size(); i++) dfs2(path[i], 0);
  memset(idOnPath, 0, sizeof(idOnPath));
  for (int i = 0; i < (int)path.size(); i++) idOnPath[path[i]] = i;
  for (int i = 0; i < T; i++) {
    memset(use, 0, sizeof(use));
    dfs3(path[0], path[0], i);
  }
  memset(use, 0, sizeof(use));
  dfs4(path[0], 0);
  data.resize(path.size());
  for (int i = 0; i < (int)path.size(); i++) data[i] = depth1[path[i]].first;
  leftttt.init(data);
  reverse(data.begin(), data.end());
  rightt.init(data);
  int len, o, w, id;
  vector<int> solveAns;
  for (int i = 0; i < m; i++) {
    v = query[i].first;
    u = query[i].second;
    v--;
    u--;
    o = getLCA(v, u);
    len = H[v] + H[u] - H[o] * 2;
    if (H[v] < H[u]) swap(v, u);
    w = getUp(v, len / 2);
    bool flag = 0;
    if (onLongestPath[w]) {
      int idv, idu, idw;
      idv = idOnPath[goToRoad[v]];
      idu = idOnPath[goToRoad[u]];
      idw = idOnPath[w];
      assert(idw != -1);
      if (idu == idw) {
        flag = 1;
      } else {
        if (idv < idu) {
          ans = max(calc(0, idw, v), calc(idw + 1, path.size() - 1, u));
        } else {
          ans = max(calc(0, idw - 1, u), calc(idw, path.size() - 1, v));
        }
      }
    } else
      flag = 1;
    if (flag) {
      if (distToPath[v] > distToPath[u]) swap(v, u);
      id = idOnPath[goToRoad[v]];
      ans = max((int)path.size() - 1 - id, id) + distToPath[v];
    }
    solveAns.push_back(ans);
  }
  return solveAns;
}
void read() {
  int v, u;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &v, &u);
    edges.push_back(make_pair(v, u));
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &v, &u);
    query.push_back(make_pair(v, u));
  }
}
void genTest() {
  int v, u;
  n = 10000;
  edges.clear();
  for (int i = 2; i <= n; i++)
    edges.push_back(make_pair(i, rand() % (i - 1) + 1));
  m = 1;
  query.clear();
  for (int i = 0; i < m; i++) {
    v = rand() % n;
    u = rand() % (n - 1);
    if (v == u) u++;
    v++;
    u++;
    query.push_back(make_pair(v, u));
  }
}
int distS[maxn][2];
bool useS[maxn][2];
vector<vector<int> > e1;
void dfsSt(int v, int h, int id) {
  useS[v][id] = 1;
  distS[v][id] = h;
  for (int i = 0; i < (int)e1[v].size(); i++)
    if (!useS[e1[v][i]][id]) {
      dfsSt(e1[v][i], h + 1, id);
    }
}
void printTest() {
  fprintf(stderr, "Test\n");
  fprintf(stderr, "%d\n", n);
  for (int i = 0; i < n - 1; i++)
    fprintf(stderr, "%d %d\n", edges[i].first, edges[i].second);
  fprintf(stderr, "%d\n", m);
  for (int i = 0; i < m; i++)
    fprintf(stderr, "%d %d\n", query[i].first, query[i].second);
}
vector<int> stupid() {
  int v, u;
  e1.resize(n);
  for (int i = 0; i < n; i++) e1[i].clear();
  for (int i = 0; i < n - 1; i++) {
    e1[edges[i].first - 1].push_back(edges[i].second - 1);
    e1[edges[i].second - 1].push_back(edges[i].first - 1);
  };
  vector<int> answer;
  for (int i = 0; i < m; i++) {
    v = query[i].first - 1;
    u = query[i].second - 1;
    for (int i = 0; i < n; i++) useS[i][0] = useS[i][1] = 0;
    dfsSt(v, 0, 0);
    dfsSt(u, 0, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, min(distS[i][0], distS[i][1]));
    answer.push_back(ans);
  }
  return answer;
}
void stress() {
  for (int t = 0; t < 20000; t++) {
    cerr << "test id: " << t << endl;
    genTest();
    vector<int> r1 = solve();
    vector<int> r2 = stupid();
    bool flag = 1;
    assert(r1.size() == r2.size());
    for (int i = 0; i < (int)r1.size(); i++)
      if (r1[i] != r2[i]) flag = 0;
    if (!flag) {
      cerr << "answer\n";
      cerr << "r1: ";
      for (int i = 0; i < (int)r1.size(); i++) fprintf(stderr, "%d ", r1[i]);
      cerr << endl;
      cerr << "r2: ";
      for (int i = 0; i < (int)r2.size(); i++) fprintf(stderr, "%d ", r2[i]);
      cerr << endl;
      printTest();
      return;
    }
  }
}
int main() {
  if (0)
    stress();
  else {
    read();
    vector<int> tmp = solve();
    for (int i = 0; i < (int)tmp.size(); i++) printf("%d\n", tmp[i]);
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

The Finals of the "Russian Code Cup" 2214 will be held in n hotels. Two hotels (let's assume that they are the main hotels), will host all sorts of events, and the remaining hotels will accommodate the participants. The hotels are connected by n - 1 roads, you can get from any hotel to any other one.

The organizers wonder what is the minimum time all the participants need to get to the main hotels, if each participant goes to the main hotel that is nearest to him and moving between two hotels connected by a road takes one unit of time.

The hosts consider various options for the location of the main hotels. For each option help the organizers to find minimal time.

Input

The first line contains an integer n (2 ≤ n ≤ 100000) — the number of hotels. The next n - 1 lines contain two integers each — the numbers of the hotels that have a road between them. Consider hotels are numbered from 1 to n.

The next line contains an integer m (1 ≤ m ≤ 100000) — the number of queries. The following m lines contains two distinct integers each — the numbers of the hotels we assume to be the main.

Output

For each request of the organizers print a single integer — the time that all participants need to reach the main hotels.

Examples

Input

3
2 3
3 1
3
2 1
2 3
3 1


Output

1
1
1


Input

4
1 4
1 2
2 3
3
1 4
1 3
2 3


Output

2
1
2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9;
const int T = 18;
struct Tree {
  vector<int> a;
  int size;
  Tree() {}
  void init(vector<int>& data) {
    size = data.size();
    a.clear();
    a.resize(size * 4);
    init2(0, 0, size, data);
  }
  void init2(int v, int ll, int rr, vector<int>& data) {
    if (ll + 1 == rr) {
      a[v] = data[ll];
      return;
    }
    init2(v * 2 + 1, ll, (ll + rr) / 2, data);
    init2(v * 2 + 2, (ll + rr) / 2, rr, data);
    a[v] = max(a[v * 2 + 1], a[v * 2 + 2] + (ll + rr) / 2 - ll);
  }
  int getMax(int l, int r) { return getMaxSeg(0, 0, size, l, r); }
  int getMaxSeg(int v, int ll, int rr, int l, int r) {
    if (ll >= r || l >= rr) return -inf;
    if (l <= ll && rr <= r) return a[v];
    int r1, r2;
    r1 = getMaxSeg(v * 2 + 1, ll, (ll + rr) / 2, l, r);
    r2 = getMaxSeg(v * 2 + 2, (ll + rr) / 2, rr, l, r);
    if (l < (ll + rr) / 2) {
      r2 += (ll + rr) / 2 - max(l, ll);
    }
    return max(r1, r2);
  }
};
vector<int> e[maxn];
int par0[maxn];
int distToPath[maxn];
int jump[maxn][T];
int tin[maxn];
int tout[maxn];
int H[maxn];
int goToRoad[maxn];
int idOnPath[maxn];
int firstChild[maxn];
pair<int, int> depth1[maxn];
pair<int, int> depth2[maxn];
vector<pair<int, int> > query;
vector<pair<int, int> > edges;
int longestPathInTree[maxn];
bool use[maxn];
bool onLongestPath[maxn];
pair<int, int> longestPath;
vector<int> path;
vector<int> data;
Tree leftttt;
Tree rightt;
int topPath = -1;
int ans;
int tmr;
int n, m;
pair<int, int> dfsLongestPath(int v) {
  pair<int, int> prT, pr1, pr2;
  pr1 = make_pair(0, v);
  pr2 = make_pair(0, v);
  use[v] = 1;
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (!use[e[v][i]]) {
      prT = dfsLongestPath(e[v][i]);
      par0[e[v][i]] = v;
      if (pr2.first < prT.first) swap(prT, pr2);
      if (pr1.first < pr2.first) swap(pr1, pr2);
    }
  }
  if (pr1.first + pr2.first > ans) {
    longestPath = make_pair(pr1.second, pr2.second);
    topPath = v;
    ans = pr1.first + pr2.first;
  }
  return make_pair(pr1.first + 1, pr1.second);
}
pair<int, int> dfs1(int v, int h, int p, int ch) {
  int newCh;
  pair<int, int> tmp;
  use[v] = 1;
  distToPath[v] = h;
  depth1[v] = depth2[v] = make_pair(0, v);
  goToRoad[v] = p;
  firstChild[v] = ch;
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (onLongestPath[e[v][i]]) continue;
    if (!use[e[v][i]]) {
      newCh = (ch == -1) ? e[v][i] : ch;
      tmp = dfs1(e[v][i], h + 1, p, newCh);
      if (tmp.first > depth2[v].first) swap(tmp, depth2[v]);
      if (depth2[v].first > depth1[v].first) swap(depth1[v], depth2[v]);
    }
  }
  return make_pair(depth1[v].first + 1, v);
}
void dfs2(int v, int wayUp) {
  int newWayUp;
  use[v] = 1;
  longestPathInTree[v] = max(depth1[v].first, wayUp);
  for (int i = 0; i < (int)e[v].size(); i++) {
    if (onLongestPath[e[v][i]]) continue;
    if (!use[e[v][i]]) {
      if (depth1[v].second == e[v][i])
        newWayUp = max(wayUp, depth2[v].first);
      else
        newWayUp = max(wayUp, depth1[v].first);
      dfs2(e[v][i], newWayUp + 1);
    }
  }
}
void dfs3(int v, int p, int id) {
  use[v] = 1;
  if (id == 0)
    jump[v][id] = p;
  else
    jump[v][id] = jump[jump[v][id - 1]][id - 1];
  for (int i = 0; i < (int)e[v].size(); i++)
    if (!use[e[v][i]]) dfs3(e[v][i], v, id);
}
void dfs4(int v, int h) {
  tin[v] = tmr++;
  H[v] = h;
  use[v] = 1;
  for (int i = 0; i < (int)e[v].size(); i++)
    if (!use[e[v][i]]) dfs4(e[v][i], h + 1);
  tout[v] = tmr++;
}
bool checkPar(int v, int u) { return tin[v] <= tin[u] && tout[u] <= tout[v]; }
int getLCA(int v, int u) {
  if (checkPar(v, u)) return v;
  if (checkPar(u, v)) return u;
  for (int i = T - 1; i >= 0; i--)
    if (!checkPar(jump[v][i], u)) v = jump[v][i];
  return jump[v][0];
}
int getUp(int v, int k) {
  for (int i = T - 1; i >= 0; i--)
    if ((1 << i) <= k) {
      v = jump[v][i];
      k -= (1 << i);
    }
  return v;
}
int calc(int l, int r, int v) {
  int idv;
  int n = path.size();
  idv = idOnPath[goToRoad[v]];
  int ans = 0;
  ans = longestPathInTree[v];
  if ((idv + 1) < (r) + 1)
    ans = max(ans, leftttt.getMax((idv + 1), (r) + 1) + 1 + distToPath[v]);
  pair<int, int> pr = make_pair(l, idv - 1);
  pr = make_pair(n - pr.first - 1, n - pr.second - 1);
  pr = make_pair(pr.second, pr.first);
  if (pr.first < pr.second + 1)
    ans = max(ans, rightt.getMax(pr.first, pr.second + 1) + 1 + distToPath[v]);
  return ans;
}
vector<int> solve() {
  int v, u;
  path.clear();
  for (int i = 0; i < n; i++) e[i].clear();
  for (int i = 0; i < (int)edges.size(); i++) {
    v = edges[i].first;
    u = edges[i].second;
    v--;
    u--;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  memset(use, 0, sizeof(use));
  topPath = -1;
  ans = 0;
  dfsLongestPath(0);
  assert(topPath != -1);
  memset(onLongestPath, 0, sizeof(onLongestPath));
  for (; longestPath.first != topPath;
       longestPath.first = par0[longestPath.first]) {
    onLongestPath[longestPath.first] = 1;
    path.push_back(longestPath.first);
  }
  vector<int> path1;
  for (; longestPath.second != topPath;
       longestPath.second = par0[longestPath.second]) {
    onLongestPath[longestPath.second] = 1;
    path1.push_back(longestPath.second);
  }
  path.push_back(topPath);
  onLongestPath[topPath] = 1;
  reverse(path1.begin(), path1.end());
  for (int i = 0; i < (int)path1.size(); i++) path.push_back(path1[i]);
  memset(use, 0, sizeof(use));
  memset(firstChild, 0, sizeof(firstChild));
  for (int i = 0; i < (int)path.size(); i++) dfs1(path[i], 0, path[i], -1);
  memset(use, 0, sizeof(use));
  for (int i = 0; i < (int)path.size(); i++) dfs2(path[i], 0);
  memset(idOnPath, 0, sizeof(idOnPath));
  for (int i = 0; i < (int)path.size(); i++) idOnPath[path[i]] = i;
  for (int i = 0; i < T; i++) {
    memset(use, 0, sizeof(use));
    dfs3(path[0], path[0], i);
  }
  memset(use, 0, sizeof(use));
  dfs4(path[0], 0);
  data.resize(path.size());
  for (int i = 0; i < (int)path.size(); i++) data[i] = depth1[path[i]].first;
  leftttt.init(data);
  reverse(data.begin(), data.end());
  rightt.init(data);
  int len, o, w, id;
  vector<int> solveAns;
  for (int i = 0; i < m; i++) {
    v = query[i].first;
    u = query[i].second;
    v--;
    u--;
    o = getLCA(v, u);
    len = H[v] + H[u] - H[o] * 2;
    if (H[v] < H[u]) swap(v, u);
    w = getUp(v, len / 2);
    bool flag = 0;
    if (onLongestPath[w]) {
      int idv, idu, idw;
      idv = idOnPath[goToRoad[v]];
      idu = idOnPath[goToRoad[u]];
      idw = idOnPath[w];
      assert(idw != -1);
      if (idu == idw) {
        flag = 1;
      } else {
        if (idv < idu) {
          ans = max(calc(0, idw, v), calc(idw + 1, path.size() - 1, u));
        } else {
          ans = max(calc(0, idw - 1, u), calc(idw, path.size() - 1, v));
        }
      }
    } else
      flag = 1;
    if (flag) {
      if (distToPath[v] > distToPath[u]) swap(v, u);
      id = idOnPath[goToRoad[v]];
      ans = max((int)path.size() - 1 - id, id) + distToPath[v];
    }
    solveAns.push_back(ans);
  }
  return solveAns;
}
void read() {
  int v, u;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &v, &u);
    edges.push_back(make_pair(v, u));
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &v, &u);
    query.push_back(make_pair(v, u));
  }
}
void genTest() {
  int v, u;
  n = 10000;
  edges.clear();
  for (int i = 2; i <= n; i++)
    edges.push_back(make_pair(i, rand() % (i - 1) + 1));
  m = 1;
  query.clear();
  for (int i = 0; i < m; i++) {
    v = rand() % n;
    u = rand() % (n - 1);
    if (v == u) u++;
    v++;
    u++;
    query.push_back(make_pair(v, u));
  }
}
int distS[maxn][2];
bool useS[maxn][2];
vector<vector<int> > e1;
void dfsSt(int v, int h, int id) {
  useS[v][id] = 1;
  distS[v][id] = h;
  for (int i = 0; i < (int)e1[v].size(); i++)
    if (!useS[e1[v][i]][id]) {
      dfsSt(e1[v][i], h + 1, id);
    }
}
void printTest() {
  fprintf(stderr, "Test\n");
  fprintf(stderr, "%d\n", n);
  for (int i = 0; i < n - 1; i++)
    fprintf(stderr, "%d %d\n", edges[i].first, edges[i].second);
  fprintf(stderr, "%d\n", m);
  for (int i = 0; i < m; i++)
    fprintf(stderr, "%d %d\n", query[i].first, query[i].second);
}
vector<int> stupid() {
  int v, u;
  e1.resize(n);
  for (int i = 0; i < n; i++) e1[i].clear();
  for (int i = 0; i < n - 1; i++) {
    e1[edges[i].first - 1].push_back(edges[i].second - 1);
    e1[edges[i].second - 1].push_back(edges[i].first - 1);
  };
  vector<int> answer;
  for (int i = 0; i < m; i++) {
    v = query[i].first - 1;
    u = query[i].second - 1;
    for (int i = 0; i < n; i++) useS[i][0] = useS[i][1] = 0;
    dfsSt(v, 0, 0);
    dfsSt(u, 0, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, min(distS[i][0], distS[i][1]));
    answer.push_back(ans);
  }
  return answer;
}
void stress() {
  for (int t = 0; t < 20000; t++) {
    cerr << "test id: " << t << endl;
    genTest();
    vector<int> r1 = solve();
    vector<int> r2 = stupid();
    bool flag = 1;
    assert(r1.size() == r2.size());
    for (int i = 0; i < (int)r1.size(); i++)
      if (r1[i] != r2[i]) flag = 0;
    if (!flag) {
      cerr << "answer\n";
      cerr << "r1: ";
      for (int i = 0; i < (int)r1.size(); i++) fprintf(stderr, "%d ", r1[i]);
      cerr << endl;
      cerr << "r2: ";
      for (int i = 0; i < (int)r2.size(); i++) fprintf(stderr, "%d ", r2[i]);
      cerr << endl;
      printTest();
      return;
    }
  }
}
int main() {
  if (0)
    stress();
  else {
    read();
    vector<int> tmp = solve();
    for (int i = 0; i < (int)tmp.size(); i++) printf("%d\n", tmp[i]);
  }
  return 0;
}

```