```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func readInt(in *bufio.Reader) int {
	var n int
	var c byte
	var err error
	for {
		c, err = in.ReadByte()
		if err != nil || (c >= '0' && c <= '9') {
			break
		}
	}
	if err != nil {
		return 0
	}
	n = int(c - '0')
	for {
		c, err = in.ReadByte()
		if err != nil || c < '0' || c > '9' {
			break
		}
		n = n*10 + int(c-'0')
	}
	return n
}

const MAX_VARS = 300005
const MAX_NODES = 2 * MAX_VARS

var (
	adj       [MAX_NODES][]int
	dfn       [MAX_NODES]int
	low       [MAX_NODES]int
	scc       [MAX_NODES]int
	inStack   [MAX_NODES]bool
	stack     []int
	callStack []frame
)

type frame struct {
	u   int
	idx int
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < MAX_NODES; i++ {
		adj[i] = make([]int, 0, 4)
	}
	stack = make([]int, 0, MAX_NODES)
	callStack = make([]frame, 0, MAX_NODES)

	t := readInt(in)
	if t == 0 {
		return
	}

	for tc := 0; tc < t; tc++ {
		n := readInt(in)
		m := readInt(in)

		edges := make([][2]int, m)
		for i := 0; i < m; i++ {
			u := readInt(in) - 1
			v := readInt(in) - 1
			edges[i] = [2]int{u, v}
		}

		if m == 0 {
			fmt.Fprintln(out, n)
			continue
		}

		solve2SAT := func(numVars int) bool {
			n_adj := numVars * 2
			for i := 0; i < n_adj; i++ {
				dfn[i] = 0
				low[i] = 0
				scc[i] = 0
				inStack[i] = false
			}
			stack = stack[:0]
			callStack = callStack[:0]
			timer := 0
			sccCount := 0

			for i := 0; i < n_adj; i++ {
				if dfn[i] == 0 {
					callStack = append(callStack, frame{u: i, idx: 0})
					for len(callStack) > 0 {
						top := len(callStack) - 1
						u := callStack[top].u
						idx := callStack[top].idx

						if idx == 0 {
							timer++
							dfn[u] = timer
							low[u] = timer
							stack = append(stack, u)
							inStack[u] = true
						}

						foundUnvisited := false
						for ; callStack[top].idx < len(adj[u]); callStack[top].idx++ {
							v := adj[u][callStack[top].idx]
							if dfn[v] == 0 {
								callStack[top].idx++
								callStack = append(callStack, frame{u: v, idx: 0})
								foundUnvisited = true
								break
							} else if inStack[v] && dfn[v] < low[u] {
								low[u] = dfn[v]
							}
						}

						if foundUnvisited {
							continue
						}

						if low[u] == dfn[u] {
							sccCount++
							for {
								v := stack[len(stack)-1]
								stack = stack[:len(stack)-1]
								inStack[v] = false
								scc[v] = sccCount
								if u == v {
									break
								}
							}
						}

						callStack = callStack[:len(callStack)-1]
						if len(callStack) > 0 {
							parent := callStack[len(callStack)-1].u
							if low[u] < low[parent] {
								low[parent] = low[u]
							}
						}
					}
				}
			}

			for i := 0; i < numVars; i++ {
				if scc[2*i] == scc[2*i+1] {
					return false
				}
			}
			return true
		}

		check := func(D int) bool {
			if D <= 1 {
				return true
			}
			W := D - 1
			numVars := 3 * n

			for i := 0; i < 2*numVars; i++ {
				adj[i] = adj[i][:0]
			}

			addImpl := func(u, v int) {
				adj[u] = append(adj[u], v)
				adj[v^1] = append(adj[v^1], u^1)
			}

			for i := 0; i < m; i++ {
				u := edges[i][0]
				v := edges[i][1]
				addImpl(2*u+1, 2*v)
			}

			for b := 0; b*W < n; b++ {
				st := b * W
				en := (b+1)*W - 1
				if en >= n {
					en = n - 1
				}
				for k := st; k <= en; k++ {
					addImpl(2*k, 2*(n+k))
					if k > st {
						addImpl(2*(n+k-1), 2*(n+k))
					}
					addImpl(2*k, 2*(2*n+k))
					if k < en {
						addImpl(2*(2*n+k+1), 2*(2*n+k))
					}
				}
			}

			for i := 0; i < n; i++ {
				L := i + 1
				R := i + W
				if R >= n {
					R = n - 1
				}
				if L >= n {
					continue
				}

				bL := L / W
				bR := R / W

				if bL == bR {
					addImpl(2*i, 2*(2*n+L)+1)
				} else {
					addImpl(2*i, 2*(2*n+L)+1)
					addImpl(2*i, 2*(n+R)+1)
				}
			}

			return solve2SAT(numVars)
		}

		lowVal := 1
		highVal := n
		ans := 1

		for lowVal <= highVal {
			mid := lowVal + (highVal-lowVal)/2
			if check(mid) {
				ans = mid
				lowVal = mid + 1
			} else {
				highVal = mid - 1
			}
		}

		fmt.Fprintln(out, ans)
	}
}
```