#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX/2;
const int maxn = 305;
namespace anna{
vector<pair<int, int>> g[maxn];
vector<long long> shortest_path(int N, int s, long long C[]){
vector<long long> d(N, INF);
vector<int> vis(N, 0);
d[s] = 0;
for(int i = 1; i <= N; i++){
long long best = INF;
int x = -1;
for(int j = 0; j < N; j++){
if(vis[j])continue;
if(d[j] < best){
best = d[j];
x = j;
}
}
if(x == -1)break;
vis[x] = 1;
for(auto v: g[x]) if(d[v.first] > C[v.second] + best)d[v.first] = C[v.second] + best;
}
return d;
}
void solve(int a, int b, int K, vector<long long>& forgor_C, vector<vector<long long>>& cost_to_T, vector<int> queries){
// eval(i, x) = forgor(x) + cost_to_T
if(queries.empty())return;
if(b == K+1){
return;
}
vector<int> a_wins, b_wins;
for(auto v: queries){
if(forgor_C[a] + cost_to_T[a][v] < forgor_C[b] + cost_to_T[b][v]) a_wins.push_back(v);
else b_wins.push_back(v);
}
int cases = queries.size() + 1, num = a_wins.size();
for(int i = 0; cases > 1; i++){
Tap(num&1);
num>>=1;
cases = (cases+1)>>1;
}
solve(a, b+1, K, forgor_C, cost_to_T, a_wins);
solve(b, b+1, K, forgor_C, cost_to_T, b_wins);
}
}
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
vector<long long> forgor_C(K+1, 0);
vector<vector<long long>> cost_to_T(K+1, vector<long long>(Q));
for(int i = 0; i < K; i++){
forgor_C[i] = C[U[i]];
}
for(int i = 0; i < K; i++)C[U[i]] = INF;
for(int i = 0; i < M; i++){
anna::g[A[i]].push_back({B[i], i});
}
for(int i = 0; i < K; i++){
auto d = anna::shortest_path(N, B[U[i]], C);
for(int j = 0; j < Q; j++)cost_to_T[i][j] = d[T[j]];
}
for(int i = 0; i < Q; i++){
auto d = anna::shortest_path(N, S[i], C);
for(int j = 0; j < K; j++)cost_to_T[j][i] += d[A[U[j]]];
cost_to_T[K][i] = d[T[i]];
}
vector<int> queries;
for(int i = 0; i < Q; i++)queries.push_back(i);
anna::solve(0, 1, K, forgor_C, cost_to_T, queries);
// eval(i, x) = forgor(x) + cost_to_A + cost_to_T
}
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 305;
const long long INF = 1e16*maxn;
namespace bruno {
vector<pair<int, int>> g[maxn];
vector<long long> shortest_path(int N, int s, long long C[]){
vector<long long> d(N, INF);
vector<int> vis(N, 0);
d[s] = 0;
for(int i = 1; i <= N; i++){
long long best = INF;
int x = -1;
for(int j = 0; j < N; j++){
if(vis[j])continue;
if(d[j] < best){
best = d[j];
x = j;
}
}
if(x == -1)break;
vis[x] = 1;
for(auto v: g[x]) if(d[v.first] > C[v.second] + best)d[v.first] = C[v.second] + best;
}
return d;
}
vector<int> qtypes[6];
vector<int> path[60];
vector<int> solve_query(int N, int s, int t, long long C[]){
vector<long long> d(N, INF);
vector<int> vis(N, 0);
vector<pair<int, int>> trace(N);
d[s] = 0;
for(int i = 1; i <= N; i++){
long long best = INF;
int x = -1;
for(int j = 0; j < N; j++){
if(vis[j])continue;
if(d[j] < best){
best = d[j];
x = j;
}
}
if(x == -1)break;
vis[x] = 1;
for(auto v: g[x]) if(d[v.first] > C[v.second] + best){
d[v.first] = C[v.second] + best;
trace[v.first] = {x, v.second};
}
}
vector<int> ans;
while(t != s){
ans.push_back(trace[t].second);
t = trace[t].first;
}
reverse(ans.begin(), ans.end());
return ans;
}
void solve(int a, int b, int K, vector<vector<long long>>& cost_to_T, vector<int> queries, int &ptr, int X[]){
// eval(i, x) = forgor(x) + cost_to_T
if(queries.empty())return;
if(b == K+1){
qtypes[a].insert(qtypes[a].end(), queries.begin(), queries.end());
return;
}
vector<int> a_wins, b_wins;
int cases = queries.size() + 1, num = 0;
for(int i = 0; cases > 1; i++){
num^=X[ptr++]<<i;
cases = (cases+1)>>1;
}
assert(num < queries.size()+1);
auto cmp = [&a, &b, &cost_to_T](int lhs, int rhs){
return cost_to_T[a][lhs] - cost_to_T[b][lhs] < cost_to_T[a][rhs] - cost_to_T[b][rhs];
};
sort(queries.begin(), queries.end(), cmp);
for(int i = 0; i < queries.size(); i++){
if(i < num)a_wins.push_back(queries[i]);
else b_wins.push_back(queries[i]);
}
solve(a, b+1, K, cost_to_T, a_wins, ptr, X);
solve(b, b+1, K, cost_to_T, b_wins, ptr, X);
}
}
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
vector<vector<long long>> cost_to_T(K+1, vector<long long>(Q));
for(int i = 0; i < K; i++)C[U[i]] = INF;
for(int i = 0; i < M; i++){
bruno::g[A[i]].push_back({B[i], i});
}
for(int i = 0; i < K; i++){
auto d = bruno::shortest_path(N, B[U[i]], C);
for(int j = 0; j < Q; j++)cost_to_T[i][j] = d[T[j]];
}
for(int i = 0; i < Q; i++){
auto d = bruno::shortest_path(N, S[i], C);
for(int j = 0; j < K; j++)cost_to_T[j][i] += d[A[U[j]]];
cost_to_T[K][i] = d[T[i]];
}
vector<int> queries;
for(int i = 0; i < Q; i++)queries.push_back(i);
int ptr = 0;
bruno::solve(0, 1, K, cost_to_T, queries, ptr, X);
for(int i = 0; i <= K; i++){
if(i < K)C[U[i]] = 0;
for(auto v: bruno::qtypes[i]){
bruno::path[v] = bruno::solve_query(N, S[v], T[v], C);
if(i == K)for(auto ele: bruno::path[v]){
for(int j = 0; j < K; j++)assert(ele != U[j]);
}
}
if(i < K)C[U[i]] = INF;
}
for(int i = 0; i < Q; i++){
for(auto v: bruno::path[i])Answer(v);
Answer(-1);
}
}
