#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
priority_queue<int, vector<int>, greater<int> >q;
int n, du[N], a[N], x;
vector<int> G[N];
int main ()
{
    n = 0;
    memset(du, 0, sizeof(du));
    while(scanf("%d",&x)!=EOF)
    {
        a[++n] = x;
        ++du[x];
    }
    n+=2;
    a[n-1]=n;du[n]++;

    for(int i = 1; i <= n; ++i)if(du[i]==0) q.push(i);
    for(int i = 1; i < n; ++i)
    {
        x = q.top(); q.pop();
        G[a[i]].push_back(x);
        G[x].push_back(a[i]);
        --du[a[i]];
        if(du[a[i]]==0) q.push(a[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        printf("%d:",i);
        sort(G[i].begin(), G[i].end());
        for(int j = 0; j < G[i].size(); ++j)
            printf(" %d",G[i][j]);
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
priority_queue<int, vector<int>, greater<int> >q;
int n, du[N], a[N], x;
vector<int>G[N];
int main ()
{
    n = 0;
	memset(du, 0, sizeof(du));
    while(scanf("%d",&x)!=EOF)
    {
        a[++n] = x;
        ++du[x];
    }
	n+=2;
	a[n-1]=n;du[n]++;

    for(int i = 1; i <= n; ++i)if(du[i]==0) q.push(i);
    for(int i = 1; i < n; ++i)
    {
        x = q.top(); q.pop();
        G[a[i]].push_back(x);
        G[x].push_back(a[i]);
        --du[a[i]];
        if(du[a[i]]==0) q.push(a[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        printf("%d:",i);
        sort(G[i].begin(), G[i].end());
        for(int j = 0; j < G[i].size(); ++j)
            printf(" %d",G[i][j]);
        printf("\n");
    }
    return 0;
}