Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.8 kB
4
Indexable
Never

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




sample
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



//////////// CODE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_SIZE 1000
#define INF 10000
using namespace std;

class Edge{
public:
	int x;
	int y;
};

Edge graph[200];
int visited[100];
int N, M;
int mi;

void DFS(int u, bool diquaTwo,int V){
	if(u == 1 && diquaTwo){
		if(mi > V){
			mi = V;
		}
		return;
	}
	if(V > mi){
		return;
	}
	++visited[u];
	for(int i = 0; i < M; ++i){
 		if(visited[graph[i].y] == 0 && u == graph[i].x){
			if(graph[i].y == 2){
				DFS(graph[i].y, true, V+1);
			}
			else{
				DFS(graph[i].y, diquaTwo, V+1);
			}
		}
		else if(visited[graph[i].y] == 1 && u == graph[i].x){
			DFS(graph[i].y, diquaTwo, V);
		}
	}
	--visited[u];
}

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 < M; ++i){
			int x, y;
			cin >> graph[i].x >> graph[i].y;
		}
		for(int i = 0; i < N; ++i){
			visited[i] = 0;
		}
		mi = INF;
		DFS(1, false, 1);
		cout << mi << endl;
	}

	return 0;
}