문제
정점이 N개인 rooted tree가 2개 있다. 각 트리의 정점은 1부터 N까지 번호가 붙어 있다.
첫 번째 트리는, i번째 정점의 부모는 Ai이다. i가 루트인 경우 Ai는 -1이다.
두 번째 트리는, i번째 정점의 부모는 Bi이다. i가 루트인 경우 Bi는 -1이다.
Sunke는 다음 조건을 만족하는 길이가 N인 수열 X1, X2, …, Xn>을 만들고 싶어 한다.
각 트리의 각 정점 i에 대해, 정점 i의 부트리에 있는 (자신을 포함한)정점들을 a1, a2, ... , ak라고 하자.
abs(Xa1 + Xa2+ … + Xak) = 1을 만족해야 한다.
이런 수열이 존재하는지의 여부를 출력하고, 존재한다면 가능한 것 중 하나를 출력하여라.
입력
첫 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 105)
두 번째 줄에 A1, A2, …, An 이 공백을 사이에 두고 주어진다. (i가 루트가 아닌 경우 1 ≤ Ai ≤ N, 루트인 경우 Ai = -1)
세 번째 줄에 B1, B2, …, Bn이 공백을 사이에 두고 주어진다. (i가 루트가 아닌 경우 1 ≤ Bi ≤ N, 루트인 경우 Bi = -1)
출력
조건을 만족하는 수열이 없다면 ‘IMPOSSIBLE’을 출력한다.
있다면 ‘POSSIBLE’을 출력한 뒤, 다음 줄에 조건을 만족하는 X1, X2, …, Xn을 출력한다.
예제 #1
5
3 3 4 -1 4
4 4 1 -1 1
POSSIBLE
1 -1 -1 3 -1
예제 #2
6
-1 5 1 5 1 3
6 5 5 3 -1 3
IMPOSSIBLE
예제 #3
8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4
POSSIBLE
1 2 -1 0 -1 1 0 -1
힌트
출처
AGC(Atcoder Grand Contest) 18
로그인해야 코드를 작성할 수 있어요.