#include "Aoi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<ll,ll>
#define vii vector<pair<ll,ll>>
#define vi vector<ll>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 1e9;
//mt19937 mt;void random_start(){mt.seed(chrono::time_poll_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MAXK = 305;
const ll MAXN = 1e4 + 5;
const ll MAXM = 2e4 + 5;
vii graf[MAXN];
ll uzyta[MAXN];
struct d{
ll v;
ll odl;
ll c;
};
struct comp{
bool operator()(const d &d1, const d &d2){
if(d1.odl != d2.odl) return d1.odl > d2.odl;
return false;
}
};
ll doktorego[MAXM];
ll krawedzdoczep[16];
ll specj[MAXM];
ll used[MAXN];
string aoi(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X){
for(auto u : X){
specj[u] = 1;
}
for(ll i = 0; i < M; ++i){
graf[A[i]].push_back({B[i], i});
graf[B[i]].push_back({A[i], i});
}
for(ll i = 0; i < N; ++i){
uzyta[i] = -1;
}
priority_queue<d, vector<d>, comp> pq;
pq.push({0, 0, 0});
while(!pq.empty()){
auto e = pq.top();
pq.pop();
if(uzyta[e.v] != -1) continue;
uzyta[e.v] = e.c;
for(auto u : graf[e.v]){
if(uzyta[u.first] != -1) continue;
pq.push({u.first, e.odl + C[u.second], u.second});
}
}
// for(int i = 0; i < N; ++i){
// cout << uzyta[i] << " P\n";
// }
for(ll i = 1; i <= Q; ++i){
// cout << i << " I\n";
ll v = T[i-1];
if(used[v] == 1){
ll tmp = v;
while(true){
if(tmp == 0){
krawedzdoczep[i] = -1;
break;
}
if(specj[uzyta[tmp]] == 1){
krawedzdoczep[i] = uzyta[tmp];
break;
}
ll d2 = A[uzyta[tmp]]; if(d2 == tmp) d2 = B[uzyta[tmp]]; tmp = d2;
}
continue;
}
while(true){
used[v] = 1;
if(v == 0) break;
ll drugi = A[uzyta[v]];
if(drugi == v) drugi = B[uzyta[v]];
// cout << v << " " << drugi << " X\n";
// cout << uzyta[v] << " G\n";
if(specj[uzyta[v]] == 1){
doktorego[uzyta[v]] = i;
}
if(used[drugi] == 1){
ll tmp = drugi;
while(true){
if(tmp == 0){
krawedzdoczep[i] = -1;
break;
}
if(specj[uzyta[tmp]] == 1){
krawedzdoczep[i] = uzyta[tmp];
break;
}
ll d2 = A[uzyta[tmp]]; if(d2 == tmp) d2 = B[uzyta[tmp]]; tmp = d2;
}
break;
}
v = drugi;
}
}
ll cnt = 1;
string s = "";
for(ll i = 0; i < K; ++i){
ll kr = X[i];
// cout << A[X[i]] << " " << B[X[i]] << " said krawedz\n";
// cout << i << " " << doktorego[X[i]] << " k\n";
for(ll j = 0; j < 5; ++j){
s += ((doktorego[kr] & (1 << j)) != 0 ? '1' : '0');
}
}
for(ll i = 2; i <= Q; ++i){
ll vl;
if(krawedzdoczep[i] == -1){
vl = 0;
}
else{
vl = doktorego[krawedzdoczep[i]];
}
// cout << i << " " << vl << " W\n";
for(ll j = 0; j < 4; ++j){
s += ((vl & (1 << j)) != 0 ? '1' : '0');
}
}
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<ll,ll>
#define vii vector<pair<ll,ll>>
#define vi vector<int>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 2e18;
//mt19937 mt;void random_start(){mt.seed(chrono::time_poll_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MAXK = 305;
const ll MAXN = 1e4 + 5;
const ll MAXM = 2e4 + 5;
ll poprz[MAXN];
vii graf2[MAXN];
vi ktore[MAXN];
ll pot2[6];
ll doktoregopodkoniec[17];
vi pomnie[17];
ll powrot[MAXN];
ll odl[MAXN];
ll tyl[MAXN];
struct d{
ll v;
ll o;
ll p;
};
struct comp{
bool operator()(const d &d1, const d &d2){
if(d1.o != d2.o) return d1.o > d2.o;
return false;
}
};
void Dijkstra(ll curr, const vector<ll> &C, const ll &N){
for(ll i = 0; i < N; ++i){
odl[i] = -1;
}
priority_queue<d, vector<d>, comp> pq;
pq.push({curr, 0, curr});
while(!pq.empty()){
auto u = pq.top();
pq.pop();
if(odl[u.v] != -1 or u.o > INF) continue;
odl[u.v] = u.o;
tyl[u.v] = u.p;
for(auto t : graf2[u.v]){
pq.push({t.first, u.o + C[t.second], u.v});
}
}
return;
}
vi drugi[MAXN];
vi ans[17];
void R(ll ind, ll curr, const vi &A, const vi &B, const vector<ll> &C, const ll &N, const ll &M){
// cout << ind << " " << curr << " H\n";
unordered_set<ll> aktywne;
for(auto u : ktore[ind]){
aktywne.insert(A[u]);
aktywne.insert(B[u]);
drugi[A[u]].push_back(B[u]);
drugi[B[u]].push_back(A[u]);
}
auto matching = [&](ll a, ll b) -> ll {
for(auto u : drugi[a]){
if(u != b) return u;
}
return -1;
};
while(aktywne.size() > 0 and curr != 0){
Dijkstra(curr, C, N);
ll mini = INF;
ll ind = -1;
for(auto u : aktywne){
if(odl[u] != -1 and odl[u] < mini){
mini = odl[u];
ind = u;
}
}
ll G = ind;
while(G != curr){
powrot[tyl[G]] = G;
G = tyl[G];
}
G = ind;
ll p = -1;
while(true){
aktywne.erase(G);
curr = G;
if(G == 0) break;
ll w = matching(G, p);
// cout << w << " " << C << " " << p << "\n";
if(w != -1){
powrot[G] = w;
p = G;
G = w;
}
else{
break;
}
}
}
if(curr != 0){
Dijkstra(curr, C, N);
ll mini = INF;
ll ind = 0;
for(auto u : ans[doktoregopodkoniec[ind]]){
if(powrot[u] != -1 and odl[u] != -1 and odl[u] < mini){
mini = odl[u];
ind = u;
}
}
ll G = ind;
while(G != curr){
powrot[tyl[G]] = G;
G = tyl[G];
}
}
for(auto u : ktore[ind]){
drugi[A[u]].clear();
drugi[B[u]].clear();
}
return;
}
map<pii, int> MAPA;
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X, string s){
pot2[0] = 1;
for(ll i = 1; i < 6; ++i){
pot2[i] = pot2[i-1] * 2;
}
for(ll i = 0; i < M; ++i){
graf2[A[i]].push_back({B[i], i});
graf2[B[i]].push_back({A[i], i});
MAPA[{A[i], B[i]}] = i;
MAPA[{B[i], A[i]}] = i;
}
for(ll i = 0; i < K; ++i){
C[X[i]] = INF;
}
ll it = 0;
for(ll i = 0; i < K; ++i){
ll vl = 0;
for(ll j = 0; j < 5; ++j){
vl += (s[it] - '0') * pot2[j];
++it;
}
if(vl == 0) continue;
ktore[vl].push_back(i);
}
for(ll i = 2; i <= Q; ++i){
ll vl = 0;
for(ll j = 0; j < 4; ++j){
vl += (s[it] - '0') * pot2[j];
++it;
}
doktoregopodkoniec[i] = vl;
}
doktoregopodkoniec[1] = 0;
for(ll i = 1; i <= Q; ++i){
pomnie[doktoregopodkoniec[i]].push_back(i);
}
for(ll i = 0; i < N; ++i){
powrot[i] = -1;
}
powrot[0] = 0;
for(int i = 1; i <= Q; ++i){
ll w = T[i-1];
if(powrot[w] == -1){
R(i, w, A, B, C, N, M);
}
ll curr = T[i-1];
while(curr != 0){
ans[i].push_back(curr);
curr = powrot[curr];
}
ans[i].push_back(0);
vi prawdziwa;
reverse(all(ans[i]));
int Y = siz(ans[i]);
for(int j = 0; j < Y-1; ++j){
prawdziwa.push_back(MAPA[{ans[i][j], ans[i][j+1]}]);
}
answer(prawdziwa);
}
return;
}
