#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

// \max[u] \min[v:leaf] dist(u, v)
// \sum[u] \min[v:leaf] dist(u, v)
namespace nearest_leaf {
pair<int, int> run() {
  queue<int> que;
  vector<int> dist(N, -1);
  for (int u = 0; u < N; ++u) if (graph[u].size() == 1) {
    dist[u] = 0;
    que.push(u);
  }
  for (; que.size(); ) {
    const int u = que.front();
    que.pop();
    for (const int v : graph[u]) if (!~dist[v]) {
      dist[v] = dist[u] + 1;
      que.push(v);
    }
  }
  int mx = 0, sum = 0;
  for (int u = 0; u < N; ++u) {
    chmax(mx, dist[u]);
    sum += dist[u];
  }
  return make_pair(mx, sum);
}
}  // nearest_leaf

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 = nearest_leaf::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[4];
int solve(const double fs[Z]) {
  if (can[0] && fs[2] < thresh(786.534, 15.5531, 1111.27, 25.7229)) return 0;
  // if (can[3] && fs[2] > thresh(1200.07, 38.5273, 1435.13, 53.7659)) return 3;
  if (can[3] && fs[2] > 1305) return 3;
  if (can[1] && fs[0] < thresh(40.4774, 3.28401, 67.1403, 9.69939)) return 1;
  // if (can[1] && fs[1] < thresh(32749, 2780.57, 50541.4, 7260.11)) return 1;
  if (can[2]) return 2;
  return 1;
}

void exper() {
  constexpr int K = 10'000;
  fill(can, can + 4, true);
  for (int t = 0; 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 == 0 || t == 1) {
        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 == 0) ? 1 : (i / 2);
          const int r = i - 1;
          ae(perm[i], perm[l + rng() % (r - l + 1)]);
        }
      } else if (t == 2) {
        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 == 3) {
        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 = 0: freq = 100000 0 0 0
  z = 0: 19 37 25.1975 2.05855
  z = 1: 14614 28463 18921.2 1389
  z = 2: 713.99 855.405 786.534 15.5531
  z = 3: 2 6 3.13944 0.354085
  z = 4: 549 736 640.516 21.3576
t = 1: freq = 0 97995 2005 0
  z = 0: 29 57 40.4774 3.28401
  z = 1: 23208 46925 32749 2780.57
  z = 2: 1005.01 1222.99 1111.27 25.7229
  z = 3: 3 10 4.44713 0.60356
  z = 4: 769 1068 905.91 34.3096
t = 2: freq = 0 623 98558 819
  z = 0: 39 125 67.1403 9.69939
  z = 1: 28704 94493 50541.4 7260.11
  z = 2: 1053.2 1392.09 1200.07 38.5273
  z = 3: 3 8 4.37894 0.583562
  z = 4: 785 1106 920.344 35.1798
t = 3: freq = 0 0 280 99720
  z = 0: 52 197 99.7902 15.828
  z = 1: 38560 149429 75556.2 12017.2
  z = 2: 1223.04 1700 1435.13 53.7659
  z = 3: 4 11 5.12949 0.724156
  z = 4: 911 1292 1074.83 44.2408
*/

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, can + 4, true);
    if (O == 1) can[2] = can[3] = false;
    if (O == 2) can[3] = false;
    if (O == 3) can[1] = 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] + 1);
    }
  }
  return 0;
}