#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// (without edge property)
// sub[u]: inside subtree at u, rooted at u
// bus[u]: outside subtree at u, rooted at par[u]
// tot[u]: rooted at u
// T: monoid representing information of a subtree.
//   T::init()  should assign the identity.
//   T::pull(const T &l, const T &r)  should assign the product.
//   T::up(int u)  should attach vertex u to the product of the subtrees.
template <class T> struct ForestDP {
  int n;
  vector<vector<int>> graph;
  vector<int> par;
  vector<T> sub, bus, tot;

  ForestDP() : n(0) {}
  explicit ForestDP(int n_) : n(n_), graph(n_) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  void run() {
    par.assign(n, -2);
    sub.resize(n);
    bus.resize(n);
    tot.resize(n);
    for (int u = 0; u < n; ++u) if (par[u] == -2) {
      dfs0(u, -1);
      dfs1(u, -1);
    }
  }
  void dfs0(int u, int p) {
    par[u] = p;
    const int deg = graph[u].size();
    int w = -1;
    for (int j = deg; --j >= 0; ) {
      const int v = graph[u][j];
      if (p != v) {
        dfs0(v, u);
        if (~w) {
          bus[v].pull(sub[v], bus[w]);
        } else {
          bus[v] = sub[v];
        }
        w = v;
      }
    }
    if (~w) {
      sub[u] = bus[w];
    } else {
      sub[u].init();
    }
    sub[u].up(u);
  }
  void dfs1(int u, int p) {
    const int deg = graph[u].size();
    int v = -1;
    for (int j = 0; j < deg; ++j) {
      const int w = graph[u][j];
      if (p != w) {
        if (~v) {
          bus[v].pull(tot[v], bus[w]);
          bus[v].up(u);
          tot[w].pull(tot[v], sub[v]);
          dfs1(v, u);
        } else {
          if (~p) {
            tot[w] = bus[u];
          } else {
            tot[w].init();
          }
        }
        v = w;
      }
    }
    if (~v) {
      bus[v] = tot[v];
      bus[v].up(u);
      tot[u].pull(tot[v], sub[v]);
      dfs1(v, u);
    } else {
      if (~p) {
        tot[u] = bus[u];
      } else {
        tot[u].init();
      }
    }
    tot[u].up(u);
  }
};

vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


constexpr int N = 1000;
const vector<vector<int>> TSS{
  {1, 2, 3, 4},
  {1, 2},
  {1, 2, 3},
  {1, 3, 4},
  {1, 2, 3, 4},
  {1, 2, 3, 4},
};

vector<vector<int>> graph;
void init() {
  graph.assign(N, {});
}
void ae(int u, int v) {
  graph[u].push_back(v);
  graph[v].push_back(u);
}

// diameter
// \sum[u] \max[v] dist(u, v)
namespace diam {
struct Data {
  int mx;
  Data() : mx(0) {}
  void init() {
    mx = 0;
  }
  void pull(const Data &l, const Data &r) {
    mx = max(l.mx, r.mx);
  }
  void up(int) {
    mx += 1;
  }
};
pair<int, int> run() {
  ForestDP<Data> f(N);
  for (int u = 0; u < N; ++u) for (const int v : graph[u]) if (u < v) f.ae(u, v);
  f.run();
  int mx = 0, sum = 0;
  for (int u = 0; u < N; ++u) {
    const int d = f.tot[u].mx - 1;
    chmax(mx, d);
    sum += d;
  }
  return make_pair(mx, sum);
}
}  // diam

// take centroid, \sum[u] log(sz[u])
namespace sum_log_sz {
vector<int> sz;
void dfs(int u, int p) {
  for (const int v : graph[u]) if (p != v) {
    dfs(v, u);
    sz[u] += sz[v];
  }
}
double run() {
  sz.assign(N, 1);
  dfs(0, -1);
  for (int u = 0; ; ) {
    int vm = -1;
    for (const int v : graph[u]) {
      if (!~vm || sz[vm] < sz[v]) vm = v;
    }
    if (!~vm || 2 * sz[vm] <= sz[u]) {
      break;
    } else {
      sz[u] -= sz[vm];
      sz[vm] += sz[u];
      u = vm;
    }
  }
  double sum = 0.0;
  for (int u = 0; u < N; ++u) sum += log((double)sz[u]);
  return sum;
}
}  // sum_log_sz

// \sum[u] [deg[u] = 1]
// \sum[u] [deg[u] = 2]
namespace small_deg {
pair<int, int> run() {
  int cnt[3] = {};
  for (int u = 0; u < N; ++u) {
    const int d = graph[u].size();
    if (d <= 2) ++cnt[d];
  }
  return make_pair(cnt[1], cnt[2]);
}
}  // small_deg

constexpr int Z = 5;
void calc(double fs[Z]) {
  const auto res01 = diam::run();
  fs[0] = res01.first;
  fs[1] = res01.second;
  fs[2] = sum_log_sz::run();
  const auto res34 = small_deg::run();
  fs[3] = res34.first;
  fs[4] = res34.second;
}

double thresh(double a, double p, double b, double q) {
  return (q * a + p * b) / (q + p);
}
bool can[5];
int solve(const double fs[Z]) {
  if (can[1] && fs[2] < thresh(786.534, 15.5531, 1111.27, 25.7229)) return 1;
  // if (can[4] && fs[2] > thresh(1200.07, 38.5273, 1435.13, 53.7659)) return 4;
  if (can[4] && fs[2] > 1305) return 4;
  if (!can[3]) return 2;
  if (!can[2]) return 3;
  return (fs[0] < 49) ? 2 : 3;
}

void exper() {
  constexpr int K = 100'000;
  fill(can + 1, can + 5, true);
  for (int t = 1; t <= 4; ++t) {
    double mn[Z], mx[Z], avg[Z] = {}, dev[Z] = {};
    fill(mn, mn + Z, +1e+100);
    fill(mx, mx + Z, -1e+100);
    int freq[4] = {};
    for (int k = 0; k < K; ++k) {
      init();
      mt19937_64 rng(k * 4 + t);
      if (t == 1 || t == 2) {
        vector<int> perm(N);
        for (int u = 0; u < N; ++u) swap(perm[rng() % (u + 1)], perm[u] = u);
        perm.insert(perm.begin(), -1);
        for (int i = 2; i <= N; ++i) {
          const int l = (t == 1) ? 1 : (i / 2);
          const int r = i - 1;
          ae(perm[i], perm[l + rng() % (r - l + 1)]);
        }
      } else if (t == 3) {
        uf.assign(N, -1);
        for (int numComps = N; numComps > 1; ) {
          const int u = rng() % N;
          const int v = rng() % N;
          if (connect(u, v)) {
            ae(u, v);
            --numComps;
          }
        }
      } else if (t == 4) {
        vector<int> seq(N - 2);
        for (int i = 0; i < N - 2; ++i) seq[i] = rng() % N;
        vector<int> deg(N, 1);
        for (int i = 0; i < N - 2; ++i) ++deg[seq[i]];
        priority_queue<int, vector<int>, greater<int>> que;
        for (int u = 0; u < N; ++u) if (deg[u] == 1) que.push(u);
        for (int i = 0; i < N - 2; ++i) {
          const int u = que.top(); que.pop();
          const int v = seq[i];
          ae(u, v);
          if (--deg[v] == 1) que.push(v);
        }
        {
          const int u = que.top(); que.pop();
          const int v = que.top(); que.pop();
          ae(u, v);
        }
      } else {
        assert(false);
      }
      
      double fs[Z] = {};
      calc(fs);
      for (int z = 0; z < Z; ++z) {
        chmin(mn[z], fs[z]);
        chmax(mx[z], fs[z]);
        avg[z] += fs[z];
        dev[z] += fs[z] * fs[z];
      }
      ++freq[solve(fs)];
    }
    cerr << "t = " << t << ": freq = "; pv(freq, freq + 4);
    for (int z = 0; z < Z; ++z) {
      avg[z] /= K;
      dev[z] /= K;
      dev[z] -= avg[z] * avg[z];
      dev[z] = sqrt(dev[z]);
      cerr << "  z = " << z << ": " << mn[z] << " " << mx[z] << " " << avg[z] << " " << dev[z] << endl;
    }
  }
}
/*
K = 10^5
t = 1: freq = 0 100000 0 0
  z = 0: 19 38 25.2003 2.05436
  z = 1: 14589 27151 18920.3 1390.38
  z = 2: 722.828 868.026 786.497 15.5442
  z = 3: 458 540 499.966 9.13046
  z = 4: 197 304 250.052 12.8512
t = 2: freq = 0 0 98994 1006
  z = 0: 29 56 40.4802 3.29369
  z = 1: 23649 45959 32748.4 2786.14
  z = 2: 1006.92 1224.94 1111.18 25.8248
  z = 3: 378 462 415.952 9.31508
  z = 4: 245 367 310.907 13.9404
t = 3: freq = 0 0 976 98486
  z = 0: 38 120 67.1043 9.65283
  z = 1: 28828 91780 50513.3 7237.84
  z = 2: 1042.7 1403.19 1199.87 38.3427
  z = 3: 363 449 406.768 9.72607
  z = 4: 261 389 324.673 14.4524
t = 4: freq = 0 0 0 378
  z = 0: 53 191 99.8819 15.8408
  z = 1: 41090 141985 75621 12025
  z = 2: 1235.47 1695.76 1435.37 53.7419
  z = 3: 329 413 368.493 9.84619
  z = 4: 299 429 367.975 15.1992
*/

int O, M;
vector<vector<int>> A, B;

int main() {
#ifdef LOCAL
  exper(); return 0;
#endif
  
  for (; ~scanf("%d", &O); ) {
    scanf("%d", &M);
    A.resize(M);
    B.resize(M);
    for (int m = 0; m < M; ++m) {
      A[m].resize(N - 1);
      B[m].resize(N - 1);
      for (int i = 0; i < N - 1; ++i) {
        scanf("%d%d", &A[m][i], &B[m][i]);
        --A[m][i];
        --B[m][i];
      }
    }
    
    fill(can + 1, can + 5, true);
    if (O == 1) can[3] = can[4] = false;
    if (O == 2) can[4] = false;
    if (O == 3) can[2] = false;
    
    vector<int> ans(M);
    for (int m = 0; m < M; ++m) {
      init();
      for (int i = 0; i < N - 1; ++i) ae(A[m][i], B[m][i]);
      double fs[Z] = {};
      calc(fs);
      ans[m] = solve(fs);
    }
    
    for (int m = 0; m < M; ++m) {
      printf("%d\n", ans[m]);
    }
  }
  return 0;
}