Untitled

Đường đi từ công ty đến nhà anh Uranus được biểu diễn bằng 1 đồ thị.

Có N đỉnh được nối với nhau bằng M đường một chiều, các đỉnh đánh số từ 1 đến N. Giả sử công ty là đỉnh 1, nhà anh Uranus - nơi tổ chức đám cưới là đỉnh 2.

Do biết trên xe là team SPen, một team rất giỏi STC ở SVMC nên bác lái xe vui tính muốn đố mọi người tìm đường đi để đi từ công ty đến đám cưới rồi quay về công ty sao cho đường đi thỏa mãn mà số các đỉnh khác nhau phải đi qua là tối thiểu.

Hãy viết chương trình giúp bác lái xe tìm đường đi trên.

Input

Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:

*Dòng 1: Số tự nhiên N và M (N<=20).

*Dòng 2..1+M: Mỗi dòng chứa 2 số nguyên khác nhau A và B (1<=A,B<=N) – biểu diễn đường đi một chiều giữa hai đỉnh A và B. Không có hai đường đi một chiều nào trùng nhau.

Output

Mỗi bộ test in trên một dòng là số đỉnh khác nhau tối thiểu phải đi qua khi đi từ đỉnh 1 đến đỉnh 2 rồi quay về 1.

Example

Input:

2

6 7

1 3

3 4

4 5

5 1

4 2

2 6

6 3

9 11

1 3

3 4

4 2

2 5

5 3

3 6

6 1

2 7

7 8

8 9

9 1

Output:

6

6
#include<iostream>
using namespace std;

int nt;
int n, m;
int map[21][21];
//int visit[21];
//int parent[21];
int dem[21];
int vx,vy;


/*class Queue {
	int arr[1000];
	int top,last;
public:
	Queue() {this->top=this->last=-1;}
	~Queue() {}
	bool isEmpty() {return this->top==this->last;}
	void push(int v) {this->arr[++this->top]=v;}
	int pop() {return this->arr[++this->last];}
	void reset() {this->top=this->last=-1;}
};

Queue q;

void restmap() {
	for(int i = 0; i <= n; i ++) {
		for(int j = 0; j <= n; j++) {
			map[i][j]= 0;
		}
	}
}

void resetvisit() {
	for(int i = 0; i <= n; i ++) {
		visit[i]= 0;
	}
}
void resetParent() {
	for(int i = 0; i <= n; i++) {
		parent[i] = 0;
	}
}
void resetDem() {
	for(int i  =0 ; i <= n; i++) {
		dem[i]=0;
	}
}

void BFS(int v) {
	q.reset();
	resetvisit();
	resetParent();
	q.push(v);
	visit[v]=1;

	while (!q.isEmpty())
	{
		v = q.pop();
		for(int i = 1; i <= n; i++) {
			if(visit[i]==0 && map[v][i]==1) {
				q.push(i);
				visit[i] = visit[v]+1;
				parent[i]=v;
				if(i==2) {
					q.reset();
					break;
				}
			}
		}
	}
}

void demso(int dau, int cuoi) {
	int ht = cuoi;
	
	do
	{
		dem[ht]++;
		ht = parent[ht];
	} while (ht != dau);
	dem[dau]++;
}*/
int mindiem = 9999999;

void restmap() {
	for(int i = 0; i <= n; i ++) {
		for(int j = 0; j <= n; j++) {
			map[i][j]= 0;
		}
	}
}
void resetDem() {
	for(int i  =0 ; i <= n; i++) {
		dem[i]=0;
	}
}
int countdiem() {
	int len = 0;
	for(int i = 1; i <= n; i++) {
		if(dem[i]!=0) {
			len++;
		}
	}
	return len;
}
void Backtrack(int v) {
	if(v==1 && dem[1]==2 && dem[2]==1) {
		int len = countdiem();
		if(len<mindiem) {
			mindiem = len;
		}
		return;
	}
	if(countdiem()>mindiem) {
		return;
	}

	for(int i = 1; i <= n; i++) {
		if(map[v][i] == 1 && ((dem[2]==1 && dem[i] < 2) || (dem[2]==0 && dem[i]<1))) {
			dem[i]++;
			Backtrack(i);
			dem[i]--;
			
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> nt;
	for(int test = 1; test <= nt; test++) {
		cin >> n >> m;
		restmap();
		resetDem();
		for(int i = 0; i < m; i++) {
			cin >> vx >> vy;
			map[vx][vy]=1;
		}
		

		/*BFS(1);
		demso(1, 2);

		
		BFS(2);
		demso(2,1);

		for(int i = 1; i <= n; i++) {
			if(dem[i]!=0) {
				len++;
			}
		}*/
		mindiem = 9999999;
		dem[1]=1;
		Backtrack(1);
		cout << mindiem << endl;
	}
	return 0;
}
Giai thich code