Untitled

package di_an_cuoi;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, check, count, res;
	static int[][] a;
	static int[] parent, visit1, visit2;

	static void BFS1(int start, int end) {
		int[] q = new int[1000];
		int front = 0, rear = 1;
		q[front] = start;
		visit1[start] = 1;
		while (front < rear) {
			int x = q[front];
			for (int i = 1; i <= n; i++) {
				if (a[x][i] == 1 && visit1[i] == 0) {
					q[rear] = i;
					rear++;
					visit1[i] = 1;
					parent[i] = x;
					if (visit1[end] == 1) {
						return;
					}
				}
			}
			front++;
		}

	}

	static void BFS2(int start, int end) {
		int[] q = new int[1000];
		int front = 0, rear = 1;
		q[front] = start;
		visit2[start] = 1;
		while (front < rear) {
			
			
			if(visit1[q[front]] == 0){
				for (int i = front; i < rear; i++) {
					if (visit1[q[i]] == 1) {
						int x = q[front];
						q[front] = q[i];
						q[i] = x;
						break;
					}
				}
			}
			
			int top = q[front];
			for (int i = 1; i <= n; i++) {
				if (a[top][i] == 1 && visit2[i] == 0) {
					q[rear] = i;
					rear++;
					visit2[i] = 1;
					parent[i] = top;
					if(visit2[end] == 1){
						return;
					}
				}
			}
			
			
			front++;
		}

	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			a = new int[n + 1][n + 1];

			for (int i = 0; i < m; i++) {
				a[scanner.nextInt()][scanner.nextInt()] = 1;
			}
			count = 0;
			parent = new int[n+1];
			visit1 = new int[n + 1];
			visit2 = new int[n + 1];
			BFS1(1, 2);
			
			visit1 = new int[n+1];
			int x = 2;
			while(x != 1){
				visit1[parent[x]] = 1;
				x = parent[x];
			}
			
//			for (int i = 1;i<=n; i++) {
//				System.out.print(visit1[i] + " ");
//			}
//			System.out.println();
			
			BFS2(2, 1);
			
			
			visit2 = new int[n+1];
			 x = 1;
			while(x != 2){
				visit2[parent[x]] = 1;
				x = parent[x];
			}
			
			visit1[1] = 1;
			visit1[2] = 1;
			
			for (int i = 1; i <= n; i++) {
				if (visit1[i] == 1 || visit2[i] == 1) {
					count++;
				}
			}

			System.out.println(count);
		}
		scanner.close();
	}
}