#include <cassert>
#include <vector>
#include <map>
#include "validation.h"
using namespace std;

bool dfs(int u, vector<int> &vis, const vector<vector<int>> &G) {
	vis[u] = 1;
	bool ret = false;
	for (int v : G[u]) {
		if (vis[v] == 0) ret = ret || dfs(v, vis, G);
		if (vis[v] == 1) ret = true;
		if (vis[v] == 2) continue;
	}
	vis[u] = 2;
	return ret;
}

int main(int argc, char **argv) {
	// Set up the input and answer streams.
	std::ifstream in(argv[1]);
	// std::ifstream ans(argv[2]); // Only for custom checker.
	OutputValidator v(argc, argv);

	int n, m;
	in >> n >> m;
	map<int, pair<int, int>> st;
	for (int id = 1, u, v; id <= m; ++id)
		in >> u >> v, st[id] = {u, v};
	assert(st.size() == m);

	int ans = v.read_long_long(0, m/2);
	v.newline();
	while (ans--) {
		int id = v.read_long_long(1, m);
		v.newline();
		auto it = st.find(id);
		if (it == st.end())
			v.WA("Duplicate removed id.");
		else
			st.erase(it);
	}

	// Now test that the edges in st are acyclic.
	vector<vector<int>> G(n);
	for (auto it : st)
		G[it.second.first-1].push_back(it.second.second-1);

	vector<int> vis(n, 0);
	for (int i = 0; i < n; ++i)
		if (vis[i] == 0)
			if (dfs(i, vis, G))
				v.WA("Resulting graph is not acyclic.");
}