Untitled

Di an cuoi
Do không trốn được Uranus nên Tomoky đành ngậm ngùi nhận thiệp và hôm nay là ngày cưới của Uranus, anh dậy từ rất sớm để đến công ty đón xe đi ăn cưới.
Đườ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
 
4
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
12 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
16 144
3 9
10 3
1 14
6 10
12 2
10 9
11 6
12 11
16 11
3 1
14 12
5 10
15 7
1 15
9 16
6 12
8 16
14 8
13 4
2 8
5 11
16 15
10 16
16 3
8 5
12 6
11 12
4 3
11 10
14 3
9 12
10 5
15 11
13 3
2 5
7 11
4 12
6 4
14 13
8 9
3 2
4 6
4 14
15 2
16 7
13 10
4 8
13 9
3 14
14 9
8 1
4 1
10 11
2 16
1 9
7 13
7 6
9 3
14 11
1 11
12 7
5 15
8 15
4 5
11 4
13 1
2 6
4 10
9 1
4 9
14 5
3 15
14 2
15 1
11 7
15 12
5 14
2 7
16 6
8 6
12 10
6 5
9 6
13 6
6 1
1 7
14 15
10 8
2 13
3 8
6 14
2 10
16 14
15 6
9 5
6 9
11 3
8 12
5 4
1 8
6 7
1 5
15 16
2 14
3 12
7 1
13 5
3 16
7 8
7 10
14 7
7 16
9 11
9 10
5 1
1 16
10 4
6 16
10 7
7 3
11 1
2 12
12 13
13 15
15 10
4 15
5 8
16 4
8 13
7 12
6 8
7 2
4 13
10 14
15 13
15 3
11 15
6 15
16 10
1 6
7 5
8 4
10 6
1 13

// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 
/*#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

using namespace std;
int N, M;
int arr[20][2];
int vis[21];
int viss[21];

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	
	ios::sync_with_stdio(false);
	
	

	//freopen("input.txt", "r", stdin);
	cin >> T;

	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 0;
		/////////////////////////////////////////////////////////////////////////////////////////////
		
		/////////////////////////////////////////////////////////////////////////////////////////////
		cin >> N >> M;
		for (int i=0;i<M;i++) {
			cin >> arr[i][0] >> arr[i][1];
		}

		// Print the answer to standard output(screen).
		cout << "#" << test_case << " " << Answer << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}*/

#include<iostream>
using namespace std;
int n, m;
int visit[21], vis[21], matrix[21][501];
int Sx[10000];
int top=-1;
int Answer, cnt;

void push(int x) {
	top++;
	Sx[top]=x;
}

void pop(int &x) {
	x=Sx[top];
	top--;
}

void dfs(int x) {
	push(x);
	vis[x] = 1;
	while(top !=-1) {
		pop(x);
		for (int i = 0; i < matrix[x][0]; i++) {
			if (visit[matrix[x][i + 1]] == 1 && vis[matrix[x][i + 1]] == 0) {
				vis[matrix[x][i + 1]] = 1;
				push(matrix[x][i + 1]);
			}
		}
	}
}

void update() {
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
	}
	dfs(1);
	if (vis[2] == 0) {
		return;
	}
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
	}
	dfs(2);
	if (vis[1] == 0) {
		return;
	}
	cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (visit[i] == 1) {
			cnt++;
		}
	}
	if (cnt < Answer) {
		Answer = cnt;
	}
}

void Try(int x) {
	for (int i = 0; i < 2; i++) {
		visit[x] = i;
		if (x == n) {
			update();
		}
		else {
			Try(x + 1);
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	freopen("input.txt", "r", stdin);
	cin >> T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 100000;
		cin >> n >> m;
		int a, b;
		for (int i = 1; i <= n; i++) {
			matrix[i][0] = visit[i] = 0;
		}
		for (int i = 0; i < m; i++) {
			cin >> a >> b;
			matrix[a][0]++;
			matrix[a][matrix[a][0]] = b;
		}
		visit[1] = 1;
		visit[2] = 1;
		Try(3);
		// Print the answer to standard output(screen).

		cout << Answer << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}

/* 6 6 10 3*/

/*#include <iostream>
using namespace std;
int n,m;
int a[21][20];
int vis[21];
int dem[21];
int kq,sum;

void backtrack(int k){
	if(vis[2]!=1&&vis[k]==2) return;
	if(vis[1]!=2&&vis[k]==3) return;
	if(vis[1]==2&&vis[2]==1){
		if(kq>sum) kq=sum;
		return;
	}
	if(sum>=kq) return;
	for(int i=0; i<dem[k]; i++){
		vis[a[k][i]]++;
		if(vis[a[k][i]]==1) sum++;
		backtrack(a[k][i]);
		vis[a[k][i]]--;
		if(vis[a[k][i]]==0) sum--;
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for (int tc=1; tc<=t;tc++){
		cin>>n>>m;
		for(int i=0; i<n; i++){
			dem[i]=0;
			vis[i]=0;
		}
		int x,y;
		for(int i=0; i<m; i++){
			cin>>x>>y;
			a[x][dem[x]]=y;
			dem[x]++;
		}
		kq=10000;
		sum=0;
		vis[1]=1;
		backtrack(1);
		cout<<kq+1<<endl;
	}
	return 0;
}*/