#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);
int count_common_roads(const std::vector<int> &r);
#else
#include "simurgh.h"
#endif
vector<int> U, V;
int N;
vector<int> trash_edges, fancy_edges;
vector<int> par;
int find_parent(int a)
{
if (par[a] == a)
return a;
return par[a] = find_parent(par[a]);
}
bool unite(int a, int b)
{
if (rand() % 2)
swap(a, b);
a = find_parent(a), b = find_parent(b);
if (a == b)
return false;
par[b] = a;
return true;
}
void reset_parent()
{
par = vector<int>(N);
for (int i = 0; i < N; i++)
par[i] = i;
}
void dfs_spanning(unordered_set<int> &edges)
{
}
bool dfs_cycle(int i, int p, vector<vector<pair<int, int>>> &adj, vector<int> &vis, unordered_set<int> &edges)
{
vis[i] = true;
for (auto [c, j] : adj[i])
{
if (c == p)
continue;
if (vis[c] || dfs_cycle(c, i, adj, vis, edges))
{
edges.insert(j);
return true;
}
}
return false;
}
int cnt_common_set(unordered_set<int> &a)
{
// if (results.count(a))
// return results[a];
return count_common_roads(vector(a.begin(), a.end()));
}
vector<vector<pair<int, int>>> build_adj(unordered_set<int> &edges)
{
vector<vector<pair<int, int>>> adj(N);
for (int i : edges)
{
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
return adj;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
U = u, V = v;
N = n;
fancy_edges = trash_edges = vector<int>(u.size());
unordered_set<int> edges;
vector<int> visited(n);
reset_parent();
for (int i = 0; i < U.size(); i++)
{
if (unite(U[i], V[i]))
edges.insert(i);
}
int base_count = cnt_common_set(edges);
for (int i = 0; i < u.size(); i++)
{
if (edges.count(i) || fancy_edges[i] || trash_edges[i])
continue;
edges.insert(i);
auto adj = build_adj(edges);
visited = vector<int>(n);
unordered_set<int> cycle_edges;
dfs_cycle(u[i], -1, adj, visited, cycle_edges);
cycle_edges.erase(i);
vector<int> stayed;
int action_stayed = 0;
for (int edge : cycle_edges)
{
if (fancy_edges[edge])
continue;
edges.erase(edge);
int new_count = cnt_common_set(edges);
if (new_count > base_count)
{ // better than other edge
trash_edges[edge] = true;
fancy_edges[i] = true;
edges.insert(i);
action_stayed = 1;
base_count = new_count;
break;
}
else if (new_count < base_count)
{
trash_edges[i] = true;
edges.erase(i);
action_stayed = -1;
edges.insert(edge);
fancy_edges[edge] = true;
break;
}
else
{
if (trash_edges[edge])
{
trash_edges[i] = true;
edges.insert(i);
action_stayed = -1;
break;
}
else
{
edges.insert(edge);
stayed.push_back(edge);
}
}
}
if (action_stayed == 0)
{
trash_edges[i] = true;
edges.erase(i);
for (int edge : stayed)
trash_edges[edge] = true;
}
else if (action_stayed == 1)
{
for (int edge : stayed)
fancy_edges[edge] = true;
}
else if (action_stayed == -1)
{
for (int edge : stayed)
trash_edges[edge] = true;
}
}
for (auto edge : edges)
fancy_edges[edge] = true;
vector<int> fancy;
for (int i = 0; i < u.size(); i++)
if (fancy_edges[i])
fancy.push_back(i);
return fancy;
}
#ifdef _DEBUG
using namespace std;
static int MAXQ = 30000;
static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
static vector<int> parent;
static int find(int node)
{
return (parent[node] == node ? node : parent[node] = find(parent[node]));
}
static bool merge(int v1, int v2)
{
v1 = find(v1);
v2 = find(v2);
if (v1 == v2)
return false;
parent[v1] = v2;
return true;
}
static void wrong_answer()
{
printf("NO\n");
exit(0);
}
static bool is_valid(const vector<int> &r)
{
if (int(r.size()) != n - 1)
return false;
for (int i = 0; i < n - 1; i++)
if (r[i] < 0 || r[i] >= m)
return false;
parent.resize(n);
for (int i = 0; i < n; i++)
{
parent[i] = i;
}
for (int i = 0; i < n - 1; i++)
{
if (!merge(u[r[i]], v[r[i]]))
{
return false;
}
}
return true;
}
static int _count_common_roads_internal(const vector<int> &r)
{
if (!is_valid(r))
wrong_answer();
int common = 0;
for (int i = 0; i < n - 1; i++)
{
bool is_common = goal[r[i]];
if (is_common)
common++;
}
return common;
}
int count_common_roads(const vector<int> &r)
{
q++;
if (q > MAXQ)
{
cout << "Too many queries!!!\n";
wrong_answer();
}
return _count_common_roads_internal(r);
}
int main()
{
// cin.tie(0);
// ios_base::sync_with_stdio(false);
freopen("/home/elias/Downloads/ioi2017tests/simurgh/tests/3-01.in", "r", stdin);
string trash;
cin >> trash;
assert(2 == scanf("%d %d", &n, &m));
assert(1 == scanf("%d", &MAXQ));
u.resize(m);
v.resize(m);
for (int i = 0; i < m; i++)
assert(2 == scanf("%d %d", &u[i], &v[i]));
goal.resize(m, false);
for (int i = 0; i < n - 1; i++)
{
int id;
assert(1 == scanf("%d", &id));
goal[id] = true;
}
vector<int> result = find_roads(n, u, v);
if (_count_common_roads_internal(result) != n - 1)
wrong_answer();
printf("OK\n");
for (int i = 0; i < (int)result.size(); i++)
{
if (i)
printf(" ");
printf("%d", result[i]);
}
printf("\n");
cout << q << "\n";
return 0;
}
#endif
