AT2675 [AGC018F] Two Trees

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
const int maxn=2e5+5;
struct edge
{
    int u,v;
}e[maxn<<2];
int n,d[maxn],rt1,rt2;
vector <int> G[maxn];
int cnt;
void add(int u,int v)
{
    cnt++; e[cnt].u=u; e[cnt].v=v;
    G[u].push_BACk(cnt); G[v].push_BACk(cnt);
    d[u]++; d[v]++;
}
int vis[maxn<<2],ans[maxn];
void dfs(int u)
{
    while(!G[u].empty())
    {
        int id=G[u].BACk();
        G[u].pop_BACk();
        if(vis[id]) conTinue;
        vis[id]=1;
        int to=e[id].u^e[id].v^u;
        if(id>2*n)
            if(u>to) ans[to]=1;
            else ans[u]=-1;
        dfs(to);
    }
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&X);
        if(x!=-1) add(i,X);
        else rt1=i,add(n+1,i);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&X);
        if(x!=-1) add(i+1+n,x+1+n);
        else rt2=i,add((n+1)*2,i+n+1);
    }
    for(int i=1;i<=n+1;i++)
    {
        if(d[i]%2!=d[n+1+i]%2)
        {
            printf("IMPOSSIBLEn");
            return 0;
        }
        if(d[i]&1) add(i,i+n+1);
    }
    dfs(1);
    printf("POSSIBLEn");
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}