/*

     题意：给一张图和一些有向边，问如何给边赋值使得d1 < d2 < .. < dx > ,,,< ddn

     贪心：左边从2开始，右边从n开始，每次选择未标记且相连的点加入树，加入时间就是d[i]，若不在树上的输出n，注意重边和重点

 */

 /************************************************

  * Author        :Running_Time

  * Created Time  :2015-8-13 12:09:17

  * File Name     :F.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 3e5 + ;

 const int MAXM = 6e5 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 vector<int> G[MAXN];

 bool vis[MAXN];

 int fa[MAXN];

 int d[MAXN];

 int u[MAXN], v[MAXN];

 int n, m;

 void mark(int u)    {

     for (int i=; i<G[u].size (); ++i)  {

         int v = G[u][i];

         if (fa[v] || vis[v])  continue;

         fa[v] = u;

     }

 }

 void work(void) {

     memset (d, , sizeof (d));

     memset (fa, , sizeof (fa));

     memset (vis, false, sizeof (vis));

     int l = , r = n, now = ;

     fa[] = ;  vis[] = true;  mark ();

     while (l <= r)  {

         if (fa[l])  {

             mark (l);   vis[l] = true;

             d[l] = ++now;   l++;   continue;

         }

         if (fa[r])  {

             mark (r);   vis[r] = true;

             d[r] = ++now;   r--;

         }

     }

     for (int i=; i<=m; ++i)    {

         if (fa[v[i]] != u[i])   printf ("%d\n", n);

         else    printf ("%d\n", abs (d[u[i]] - d[v[i]]));

     }

 }

 int main(void)    {     //HDOJ 5385 The Path

     int T;  scanf ("%d", &T);

     while (T--) {

         scanf ("%d%d", &n, &m);

         for (int i=; i<=n; ++i)    G[i].clear ();

         for (int i=; i<=m; ++i)    {

             scanf ("%d%d", &u[i], &v[i]);

             G[u[i]].push_back (v[i]);

         }

         work ();

     }

     return ;

 }