subject (aside from precisely one), there exists an essential theme (for the point I, the essential point is pi). Ivan can't give a talk on a subject prior to giving a talk on its essential theme. There exists no less than one substantial requesting of themes as per these essential imperatives. Requesting the subjects effectively can assist understudies with understanding the talks better. Ivan has k uncommon sets of points
Correct answer will be upvoted else Multiple Downvoted. Computer science.
every subject (aside from precisely one), there exists an essential theme (for the point I, the essential point is pi). Ivan can't give a talk on a subject prior to giving a talk on its essential theme. There exists no less than one substantial requesting of themes as per these essential imperatives.
Requesting the subjects effectively can assist understudies with understanding the talks better. Ivan has k uncommon sets of points (xi,yi) with the end goal that he realizes that the understudies will comprehend the yi-th subject better if the talk on it is led just after the talk on the xi-th theme. Ivan needs to fulfill the requirements on each such pair, that is, for each i∈[1,k], there should exist some j∈[1,n−1] to such an extent that qj=xi and qj+1=yi.
Presently Ivan needs to know whether there exists a requesting of subjects that fulfills this multitude of imperatives, and if something like one exists, track down any of them.
Input
The primary line contains two integers n and k (2≤n≤3⋅105, 1≤k≤n−1) — the number of points and the number of uncommon sets of subjects, separately.
The subsequent line contains n integers p1, p2, ..., pn (0≤pi≤n), where pi is the essential subject for the theme I (or pi=0 if the I-th point has no essential themes). Precisely one of these integers is 0. Somewhere around one requesting of subjects with the end goal that for each I the pi-th theme is set before the I-th point exists.
Then, at that point, k lines follow, the I-th line contains two integers xi and yi (1≤xi,yi≤n; xi≠yi) — the subjects from the I-th extraordinary pair. All upsides of xi are pairwise unmistakable; correspondingly, all valus of yi are pairwise particular.
Output
In case there is no requesting of subjects meeting every one of the requirements, print 0.
In any case, print n pairwise particular integers q1, q2, ..., qn (1≤qi≤n) — the requesting of points meeting the limitations in general. In case there are different replies, print any of them.
Step by step
Solved in 4 steps with 1 images
