E. Plan of Lectures

Ivan is a programming teacher. During the academic year, he plans to give ?? lectures on ?? different topics. Each topic should be used in exactly one lecture. Ivan wants to choose which topic will he explain during the 1-st, 2-nd, ..., ??-th lecture — formally, he wants to choose some permutation of integers from 1 to ?? (let's call this permutation ??). ???? is the index of the topic Ivan will explain during the ??-th lecture.

For each topic (except exactly one), there exists a prerequisite topic (for the topic ??, the prerequisite topic is ????). Ivan cannot give a lecture on a topic before giving a lecture on its prerequisite topic. There exists at least one valid ordering of topics according to these prerequisite constraints.

Ordering the topics correctly can help students understand the lectures better. Ivan has ?? special pairs of topics (????,????) such that he knows that the students will understand the ????-th topic better if the lecture on it is conducted right after the lecture on the ????-th topic. Ivan wants to satisfy the constraints on every such pair, that is, for every ??∈[1,??], there should exist some ??∈[1,???1] such that ????=???? and ????+1=????.

Now Ivan wants to know if there exists an ordering of topics that satisfies all these constraints, and if at least one exists, find any of them.

Input

The first line contains two integers ?? and ?? (2≤??≤3?105, 1≤??≤???1) — the number of topics and the number of special pairs of topics, respectively.

The second line contains ?? integers ??1, ??2, ..., ???? (0≤????≤??), where ???? is the prerequisite topic for the topic ?? (or ????=0 if the ??-th topic has no prerequisite topics). Exactly one of these integers is 0. At least one ordering of topics such that for every ?? the ????-th topic is placed before the ??-th topic exists.

Then ?? lines follow, the ??-th line contains two integers ???? and ???? (1≤????,????≤??; ????≠????) — the topics from the ??-th special pair. All values of ???? are pairwise distinct; similarly, all valus of ???? are pairwise distinct.

Output

If there is no ordering of topics meeting all the constraints, print 0.

Otherwise, print ?? pairwise distinct integers ??1, ??2, ..., ???? (1≤????≤??) — the ordering of topics meeting all of the constraints. If there are multiple answers, print any of them.

Examples

input

5 2

2 3 0 5 3

1 5

5 4

output

3 2 1 5 4

題意

有一個人在講課，會講n門課。

對于每門課i，他必須在第pi門課講完后才能講。其中僅有一門課的pi為0，表示沒有需要提前講的。保證不成環(huán)。

現(xiàn)在還有k個強條件，每個條件會給xi，yi。表示講第xi門課后的下一節(jié)課必須講第yi門課；保證xi!=xj,yi!=yj。

問你是否有合法解，有的話就任意輸出一個即可。

題解

首先這道題的題意需要理解一下：

第一個條件相當(dāng)于給了你一棵樹。

第二個條件給了你若干條鏈或者環(huán)，如果存在環(huán)直接輸出非法即可。（一定是鏈或者環(huán)，因為xi!=xj,yi!=yj，不會有多個點指向同一個點）。

然后這道題因為鏈里面的點必須強制按照順序輸出，那么我們直接將鏈進(jìn)行縮點，然后將樹根據(jù)縮點后的結(jié)果變成一個DAG，然后跑一個拓?fù)渑判蛑苯虞敵黾纯伞?/p>

非法的情況是：強條件中存在環(huán)；強條件中順序和樹上順序沖突；形成的DAG里面有環(huán)。

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+7;
vector<int>G[maxn];
int n,k,fa[maxn],nxt[maxn];
int L[maxn],id,rnk[maxn],vis[maxn],rt[maxn],R,ind[maxn];
int main() {
	cin>>n>>k;
	for (int i=1;i<=n;i++) {
		int x;cin>>x;
		fa[i]=x;
		if (x==0) R=i;
	}
	for (int i=1;i<=k;i++) {
		int x,y;
		cin>>x>>y;
		nxt[x]=y;
		vis[y]=1;
	}
	for (int i=1;i<=n;i++) {
		if (vis[i]) continue;
		L[i]=++id;
		int now=0,x=nxt[i];
		rnk[i]=now;
		rt[id]=i;
		while(x!=0&&L[x]==0) {
			L[x]=id;
			rnk[x]=++now;
			x=nxt[x];
		}
	}

	// check circle pass
	for (int i=1;i<=n;i++) {
		if (!L[i]) {
			cout<<"0"<<endl;
			return 0;
		}
		if (L[i]==L[fa[i]]&&rnk[i]<rnk[fa[i]]) {
			cout<<"0"<<endl;
			return 0;
		}
	}

	for (int i=1;i<=n;i++) {
		if (fa[i]==0)continue;
		if (L[fa[i]] != L[i]) {
			G[L[fa[i]]].push_back(L[i]);
			ind[L[i]]++;
		}
	}

	vector<int> ans;
	queue<int> Q;
	for (int i=1;i<=id;i++) {
		if (ind[i]==0) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int now = Q.front();
		Q.pop();
		ans.push_back(now);
		for (int i=0;i<G[now].size();i++) {
			int v = G[now][i];
			ind[v]--;
			if (ind[v]==0) {
				Q.push(v);
			}
		}
	}
	if (ans.size()==id) {
		// for (int i=0;i<ans.size();i++) {
		//     cout<<"---- " << ans[i]<< " " << rt[ans[i]] << endl;
		// }
		for (int i=0;i<ans.size();i++) {
			int now = rt[ans[i]];
			int ID = L[rt[ans[i]]];
			while(now&&ID==L[now]) {
				cout<<now<<" ";
				now=nxt[now];
			}
		}
		cout<<endl;
		return 0;
	}
	cout<<"0"<<endl;
}