Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define MAX 21
int A[MAX], B[MAX], map[MAX][MAX], visited[MAX];
int N, M;
int ans;
struct Position {
	int x;
};

class Queue {
	int front, rear;
	Position arr[2000000];
public:
	Queue() { front = 0; rear = 0; };
	void push(Position val) {
		arr[rear++] = val;
	};
	Position pop() {
		return arr[front++];
	};
	bool isEmpty() {
		return front == rear;
	};
	void reset() {
		front = 0;
		rear = 0;
	}

};

Queue q;

void resetV() {
	for (int j = 1; j <= M; j++)
	{
		visited[j] = 0;
	}
}

int bfsDi(int N, int map[MAX][MAX], int start) {
	resetV();
	int count = 0;
	q.reset();
	Position positionPush = { start };
	q.push(positionPush);
	visited[start] = 1;
	while (!q.isEmpty()) {
		Position positionPop = q.pop();
		count++;
		for (int i = 1; i <= N; i++)
		{
			
			if (map[positionPop.x][i] == 1 && visited[i] == 0) {
				Position positionPush = { i };
				q.push(positionPush);
				visited[i] = 1;
				if (visited[2] == 1) {
					return count;
					break;
				}
			}

			
		}
	}

}

int bfsVe(int N, int map[MAX][MAX], int end) {
	resetV();
	int count = 0;
	q.reset();
	Position positionPush = { end };
	q.push(positionPush);
	visited[end] = 1;
	while (!q.isEmpty()) {
		Position positionPop = q.pop();
		count++;
		for (int i = 1; i <= N; i++)
		{
			if (map[i][positionPop.x] == 1 && visited[i] == 0) {
				Position positionPush = { i };
				q.push(positionPush);
				visited[i] = 1;
				if (visited[1] == 1) {
					return count;
					break;
				}
			}

			
		}
	}

}



void init() {
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			map[i][j] = 0;
			visited[j] = 0;
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++)
	{
		cin >> N >> M;
		init();
		for (int i = 1; i <= M; i++)
		{
			cin >> A[i];
			cin >> B[i];
		}
		for (int j = 1; j <= M; j++)
		{
			map[A[j]][B[j]] = 1;
		}

		int minDi = bfsDi(N, map,1);
		int minVe = bfsVe(N, map,2);
		cout << minDi + minVe << endl;
	}
	return 0;
}