정점이 N개인 rooted tree가 2개 있다. 각 트리의 정점은 1부터 N까지 번호가 붙어 있다.

첫 번째 트리는, i번째 정점의 부모는 A_i이다. i가 루트인 경우 A_i는 -1이다.

두 번째 트리는, i번째 정점의 부모는 B_i이다. i가 루트인 경우 B_i는 -1이다.

Sunke는 다음 조건을 만족하는 길이가 N인 수열 X₁, X₂, …, X_n>을 만들고 싶어 한다.

각 트리의 각 정점 i에 대해, 정점 i의 부트리에 있는 (자신을 포함한)정점들을 a₁, a₂, ... , a_k라고 하자.

abs(X_a1 + X_a2+ … + X_ak) = 1을 만족해야 한다.

이런 수열이 존재하는지의 여부를 출력하고, 존재한다면 가능한 것 중 하나를 출력하여라.

Two Trees timer 1s memory 256MB

Two Trees 1s 256MB