l1.cpp

#include<cstdio>
#include<vector>
#include<iostream>
#include<queue>
#define INF 2000000000
#define MAX 700
using namespace std;

struct edge {
	int x, y;
	edge(int _x, int _y) { x = min(_x, _y); y = max(_x, _y);}
};

struct vertex {
	int x, c;
	vertex(int _x, int _c) { x = _x; c = _c; }
};

int Z, N, K, L, Q, M, a, b, c, x, y, result;
int dist[MAX][MAX];
vector<vertex> vertices[MAX];
int colors[MAX];
queue<edge> edges;

void load_data();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data();
    calculate();
    print_data();
  }
  return 0;
}

int read_distance(int x, int y) {
	return dist[min(x, y)][max(x, y)];
}

int set_distance(int x, int y, int v) {
	return dist[min(x, y)][max(x, y)] = v;
}

void load_data() {
  scanf("%d %d %d %d", &N, &K, &L, &Q);

  for (int i = 1; i <= N; ++i) {
		vertices[i].clear();
		for(int j = i+1; j <= N; ++j)	set_distance(i, j, INF);
  }

	for(int i = 1; i <= N; ++i) scanf("%d", &colors[i]);
	
	scanf("%d", &M);
	for(int i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		vertices[a].push_back(vertex(b, c));
	}
	
	while(!edges.empty()) edges.pop();
	result = -1;
}

void BFS(int _x, int _y, bool first) {
	for(int i = 0; i < vertices[_x].size(); ++i) {
		if(vertices[_x][i].c == colors[_y] && read_distance(_y, vertices[_x][i].x) == INF) {
			set_distance(_y, vertices[_x][i].x, dist[first ? _x : _y][first ? _y : _x] + 1);
			edges.push(edge(_y, vertices[_x][i].x));
		}
	}
}

void calculate() {
	edges.push(edge(K, L));
	dist[min(K, L)][max(K, L)] = 0;
	
	while(!edges.empty()) {
		x = edges.front().x;
		y = edges.front().y;
		edges.pop();
		
		if(x == Q || y == Q) {
			result = dist[x][y];
			break;
		}
		
		BFS(x, y, true);
		BFS(y, x, false);
	}
}

void print_data() {
	if (result > -1) printf("%d\n", result);
	else printf("NIE\n");
}