題干：

In Summer Informatics School, if a student doesn't behave well, teachers make a hole in his badge. And today one of the teachers caught a group of?nn?students doing yet another trick.

Let's assume that all these students are numbered from?11?to?nn. The teacher came to student?aa?and put a hole in his badge. The student, however, claimed that the main culprit is some other student?papa.

After that, the teacher came to student?papa?and made a hole in his badge as well. The student in reply said that the main culprit was student?ppappa.

This process went on for a while, but, since the number of students was finite, eventually the teacher came to the student, who already had a hole in his badge.

After that, the teacher put a second hole in the student's badge and decided that he is done with this process, and went to the sauna.

You don't know the first student who was caught by the teacher. However, you know all the numbers?pipi. Your task is to find out for every student?aa, who would be the student with two holes in the badge if the first caught student was?aa.

Input

The first line of the input contains the only integer?nn?(1≤n≤10001≤n≤1000)?— the number of the naughty students.

The second line contains?nn?integers?p1p1, ...,?pnpn?(1≤pi≤n1≤pi≤n), where?pipi?indicates the student who was reported to the teacher by student?ii.

Output

For every student?aa?from?11?to?nn?print which student would receive two holes in the badge, if?aa?was the first student caught by the teacher.

Examples

Input

3 2 3 2

Output

2 2 3

Input

3 1 2 3

Output

1 2 3

Note

The picture corresponds to the first example test case.

When?a=1a=1, the teacher comes to students?11,?22,?33,?22, in this order, and the student?22?is the one who receives a second hole in his badge.

When?a=2a=2, the teacher comes to students?22,?33,?22, and the student?22?gets a second hole in his badge. When?a=3a=3, the teacher will visit students?33,?22,?33?with student?33getting a second hole in his badge.

For the second example test case it's clear that no matter with whom the teacher starts, that student would be the one who gets the second hole in his badge.

題目大意：

在圖靈學校，如果一個學生表現不好，老師就會在他的徽章上打一個洞。今天，老師逮到了n名學生在搞惡作劇。

這些學生從1到n編號。老師先逮到了a學生然后在他的徽章上打了個洞。但是這個學生說帶頭的是另一個學生pa。

于是老師又抓住學生pa在他的徽章上也打了個洞。這個學生又說其實是學生ppa在帶頭搞惡作劇。

這個過程一直持續了好一會兒，不過因為這些學生是有限的，最后老師抓住了一個徽章上已經有一個洞的學生。

在給這個倒霉孩子的徽章上又打了個洞以后，老師覺得有點累，需要蒸個桑拿于是他就不再繼續了。

你不知道誰是老師逮到的第一個學生，但是你知道所有的數字pi。對于每一個a，如果第一個被逮到的學生是a，你的任務是找到誰會是徽章上面有兩個洞的學生。

解題報告：

? ? 用數組去存這條有向邊就行了（因為邊數就一條），所以不需要去建圖。（當然這題還有一種O(n)的做法）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n,a[MAX]; bool vis[MAX]; int main() {cin>>n; for(int i = 1; i<=n; i++) cin>>a[i];for(int i = 1; i<=n; i++) {int cur = i;memset(vis,0,sizeof vis);while(1) {if(vis[cur]) break;vis[cur] = 1;cur = a[cur];}printf("%d ",cur);}return 0 ; }

這題還有一個O(n)的解法：

? 因為不難發現，如果一個節點在一個環上，那么答案就是這個節點。反之，那就是在距離這個節點最近的環首上。對于環的問題我們可以拓撲排序一下，然后用并查集去尋找最近的一個環。

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5;int a[MAX], in[MAX], f[MAX];int getf(int i) {return (i==f[i] ? i : f[i] = getf(f[i])); }int main() {int n;cin>>n;for(int i = 1; i<=n; i++) {cin>>a[i];in[a[i]]++;}queue<int> q;for(int i = 1; i<=n; i++)f[i] = i;for(int i = 1; i<=n; i++)if(in[i]==0)q.push(i);//做拓撲排序，使得剩下的頂點都在環中while(!q.empty()) {int cur = q.front();q.pop();in[a[cur]]--;f[cur] = a[cur];if(in[a[cur]]==0) q.push(a[cur]);}for(int i = 1; i<=n; i++) printf("%d ",getf(i));return 0; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1020B】Badge（模拟，图，环）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。