Untitled

He thong dien
Sau khi anh VenG đã xây dựng đường đi giữa những hòn đảo, anh Eagle được cử sang để xây dựng hệ thống điện giữa các hòn đảo cho người dân, do muốn ăn bớt kinh phí nên anh Eagle không xây dựng trạm phát điện trên tất cả các đảo mà chỉ xây trên 1 số đảo nhất định. Các đảo kết nối với nhau thành 1 mạng lưới điện. Rõ ràng những đảo nào ở càng xa nguồn phát thì điện sẽ càng yếu.
Để đảm bảo người dân không than phiền điện yếu, nên anh Eagle muốn tính toán xem điện ở đảo nào sẽ yếu nhất.
Độ yếu của điện tại đảo X được tính bằng 0 nếu đảo đó có trạm phát điện, nếu đảo X có kết nối điện với đảo Y mà đảo Y ở gần trạm phát hơn, độ yếu tại đảo X = độ yếu tại đảo Y + 1. Nếu đảo X không có điện thì có độ yếu bằng vô cùng (infinity).
Input
Dòng đầu tiên chứa số testcase T.
Mỗi test case gồm:
Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số đảo, M là số đảo có trạm phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).
Dòng tiếp theo gồm M số là ID các đảo có máy phát điện (ID đánh số từ 0 tới N-1).
H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết đảo u có kết nối với đảo v.
 
Output
In ra đảo độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra đảo có ID nhỏ nhất.
Example
Input:
2
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
6 2 3
5 2
0 5
0 1
3 4
 
Output:
 
1
3

15
2 1 0
0
2 1 0
1
2 1 1
1
0 1
10 2 7
0 9
1 2
3 4
5 6
7 8
2 3
4 5
6 7
10 2 8
0 1
0 2
3 4
5 6
7 9
2 3
4 5
6 7
1 8
10 9 9
0 1 2 3 4 5 6 7 8
0 9
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
10 5 20
1 4 3 7 8
1 5
5 8
5 6
4 8
5 7
2 7
0 7
2 9
4 7
6 8
5 9
6 9
7 9
2 5
1 2
0 5
1 8
2 3
0 2
4 5
50 2 20
14 27
2 9
1 28
25 47
16 18
13 37
29 48
14 39
5 27
35 44
34 40
19 36
4 9
15 24
11 12
6 23
16 24
20 39
11 48
9 29
14 25
50 1 200
15
14 30
7 48
4 9
36 47
0 16
6 23
17 42
39 42
9 21
37 42
1 12
12 42
32 44
22 29
2 43
5 11
0 1
30 38
25 46
27 37
34 44
12 40
30 43
22 30
13 32
27 31
34 45
38 49
33 49
33 38
28 30
17 31
2 5
7 37
39 43
0 12
20 45
1 36
33 48
0 29
6 45
39 41
19 44
21 32
3 32
33 47
31 41
13 36
16 25
4 5
27 28
9 40
3 42
11 46
14 25
28 42
6 33
3 18
37 40
5 15
35 44
12 41
21 36
7 12
10 39
2 28
16 31
3 41
5 40
30 37
16 34
4 29
24 48
11 39
47 48
9 49
37 38
6 30
22 36
8 41
19 26
43 49
36 43
9 12
10 43
19 37
3 26
16 19
11 15
30 33
11 37
20 22
21 35
3 19
30 31
16 48
15 31
28 49
10 45
26 46
24 26
14 28
5 42
11 49
40 42
12 35
4 39
4 25
13 30
8 21
29 44
23 36
26 29
1 48
12 46
0 36
8 30
6 8
9 25
0 15
6 49
13 19
2 16
7 36
18 19
16 26
24 41
0 47
16 28
21 30
20 41
44 45
23 49
36 39
7 33
45 48
23 38
19 29
28 31
4 42
12 19
9 34
34 39
34 37
2 27
2 49
30 45
14 39
12 20
29 47
8 36
13 24
2 18
9 48
11 30
3 22
47 49
20 37
13 39
29 48
9 41
18 20
5 7
29 34
9 43
23 44
7 16
10 30
27 45
32 35
4 30
15 16
38 43
11 21
31 39
1 14
8 22
9 16
25 47
17 21
24 25
25 31
15 28
20 28
16 35
8 44
32 41
1 8
32 38
24 28
17 37
16 23
6 21
2 4
2 36
22 48
33 42
27 32
17 25
15 23

// 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, H;
int a, b, elec;
int vis[1000];
int mtk[1000][1000];
//int elec[10000];
int Qx[100000];
int front, rear;
//int Max;
int rs;

void push(int x) {
	rear++;
	Qx[rear]=x;
}
int pop() {
	front++;
	return Qx[front];
}

void bfs() {
	while (front < rear) {
		int x = pop();
		if (front == rear) {
			front = rear = 0;
		}
		for (int i=0;i<N;i++) {
			if (mtk[x][i] == 1 ) {
				if (vis[i] == 10000) {
					vis[i] = vis[x] + 1;
					push(i);
				}
			}
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	int Max;
	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 >> H;
		for (int i=0;i<N;i++) {
			vis[i]=10000;
			for (int j=0;j<N;j++) {
				mtk[i][j]=0;
			}
		}
		for (int i=0;i<M; i++) {
			cin >> elec;
			vis[elec]=0;
			push(elec);
		}
		for (int i=0; i<H;i++) {
			cin >> a >> b;
			mtk[a][b]=1;
			mtk[b][a]=1;
		}		
		bfs();
		Max=0;
		for (int i=0; i<N; i++) {
			if (vis[i] > Max) {
				Max = vis[i];
				Answer = i;
			}
		}
		// Print the answer to standard output(screen).
		cout << Answer << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}


/*#include<iostream>
using namespace std;
int n, m, h;
int island[1000], matrix[1000][1000];
int queue[100000];
int front, rear;

void bfs() {
	while (front < rear) {
		int x = queue[front];
		front++;
		if (front == rear) {
			front = rear = 0;
		}
		for (int i = 0; i < n; i++) {
			if (matrix[x][i] == 1) {
				if (island[i] == 10000) {
					island[i] = island[x] + 1;
					queue[rear] = i;
					rear++;
				}
			}
		}
	}
}

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


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

	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 0;
		cin >> n >> m >> h;
		for (int i = 0; i < n; i++) {
			island[i] = 10000;
			for (int j = 0; j < n; j++) {
				matrix[i][j] = 0;
			}
		}
		front = rear = 0;
		for (int i = 0; i < m; i++) {
			int a;
			cin >> a;
			island[a] = 0;
			queue[rear] = a;
			rear++;
		}
		for (int i = 0; i < h; i++) {
			int a, b;
			cin >> a >> b;
			matrix[a][b] = 1;
			matrix[b][a] = 1;
		}
		bfs();
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (island[i] > max) {
				max = island[i];
				Answer = i;
			}
		}
		// Print the answer to standard output(screen).
		cout << Answer << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}*/