Untitled

----dams 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
------ dao----------
import java.io.FileInputStream;
import java.util.Scanner;

class nuoc_bien {

	static int n, m, count;
	static int map[][] = new int[100][100];
	static int visit[][] = new int[100][100];
	static Queue q1 = new Queue();
	static Queue q2 = new Queue();

	static boolean check() {
		int c = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] > 0)
					c++;
				if (c > 1)
					return false;
			}
		}
		return true;
	}

	static void update_map() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] -= 1;
			}
		}
	}

	static boolean calc() {
		boolean ck = true;
		while (ck) {
			update_map();
			count++;
			if (check()) {
				return true;

			}
			if (bfs())
				return true;

		}
		return false;
	}

	static boolean bfs() {
		reset_visit();
		int c = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] > 0 && visit[i][j] == 0) {
					q1.reset();
					q1.push(i);
					q2.reset();
					q2.push(j);
					visit[i][j] = 1;
					while (!q1.isEmpty()) {
						int pR = q1.pop();
						int pC = q2.pop();

						for (int i1 = 0; i1 < n; i1++) {
							for (int j1 = 0; j1 < m; j1++) {
								if (map[i1][j1] > 0 && visit[i1][j1] == 0) {
									q1.push(i1);
									q2.push(j1);
									visit[i1][j1] = 1;
								}
							}
						}
					}
					c++;
					if (c > 1)
						return true;
				}
			}
		}
		return false;

	}

	static void reset_visit() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visit[i][j] = 0;
			}
		}
	}

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("nuoc_bien.txt"));

		Scanner sc = new Scanner(System.in);

		while (true) {
			n = sc.nextInt();
			m = sc.nextInt();

			if (n == 0 && m == 0)
				return;
			map = new int[n][m];
			visit = new int[n][m];

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = sc.nextInt();

				}

			}

			count = 0;
			boolean ans = calc();
			if (!ans) {
				System.out.println("Island splits when ocean rises " + count
						+ " feet.");
			} else {
				System.out.println("Island never splits.");
			}

		}
	}

	static class Queue {
		static int MAX = 100000;
		static int[] A = new int[MAX];

		static int front = 0;
		static int rear = -1;

		boolean isEmpty() {
			if (front > rear)
				return true;
			return false;
		}

		boolean isfull() {
			if (rear == MAX - 1)
				return true;
			return false;
		}

		void push(int a) {
			if (!isfull()) {
				rear++;
				A[rear] = a;
			}
		}

		int pop() {
			if (!isEmpty()) {
				front++;
				return A[front - 1];
			}
			return -1;
		}

		void reset() {
			front = 0;
			rear = -1;
		}
	}

}
---------------
tuan trang mat---------------
-----------------
Tuần Trăng Mật
Tuần trăng mật

Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.

Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).

Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.

Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:

• Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15).

• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.

• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9.

Output

In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.

Example

Input:

1

6 8 2

2 5

1 2 4

2 4 2

4 3 3

3 1 4

4 1 5

3 5 5

5 3 1

5 6 7

 Output:

Case #1

19



Case #2

57