모빌

어린 남동생 Ike에게 줄 선물을 고르고 있다. Ike는 특정한 형태의 모빌만 좋아한다.

모빌은 여러 층으로 이루어진 장식으로, 보통 천장에 매달아 놓는다. 모빌은 여러 개의 수평 막대로 구성되며, 각 막대의 양 끝(왼쪽 끝과 오른쪽 끝)에는 줄이 하나씩 매여 있다. 각 줄의 끝에는 또 다른 막대가 매달려 있거나, 아니면 장난감이 하나 매달려 있다. 따라서 모빌은 각 막대가 정확히 두 개의 자식(막대 또는 장난감)을 갖는 이진 트리 구조를 이룬다.

Ike를 만족시키려면 다음 두 조건을 모두 만족하도록 모빌을 바꿀 수 있어야 한다.

(i) 모든 장난감이 같은 레벨에 있거나, 레벨이 서로 다른 두 장난감이 있다면 그 레벨 차이가 정확히 1이어야 한다. (장난감의 레벨이란 그 장난감에서 천장까지 이어지는 경로에 놓인 수평 막대의 개수이다.)

(ii) 레벨이 서로 다른 두 장난감이 있을 때, 왼쪽에 있는 장난감이 오른쪽에 있는 장난감보다 더 아래(즉 더 큰 레벨)에 있어야 한다.

막대 하나의 양 끝은 서로 맞바꿀 수 있다. 즉, 막대의 왼쪽 끝과 오른쪽 끝에 매인 줄을 풀어 서로 반대쪽 끝에 다시 매는 것이다. 이 작업은 그 아래에 매달린 막대나 장난감들의 내부 구성은 바꾸지 않고, 해당 막대의 왼쪽 서브트리와 오른쪽 서브트리만 통째로 맞바꾼다.

예를 들어, 조건 (i)은 만족하지만 조건 (ii)는 만족하지 않는 모빌을 생각해 보자. 가장 왼쪽에 있는 장난감이 오른쪽에 있는 장난감들보다 더 높은(레벨이 더 작은) 위치에 있다면 조건 (ii)에 어긋난다. 이때 맨 위 막대(1번 막대)의 양 끝을 맞바꾸어 2번 막대와 3번 막대의 위치를 서로 바꾸고, 이어서 2번 막대의 양 끝을 맞바꾸어 그 아래 막대와 장난감의 좌우를 바꾸면 두 조건을 모두 만족하는 모빌이 된다. 이 경우 필요한 맞바꿈은 모두 2번이다.

주어진 모빌을 Ike가 좋아하는 형태로 바꿀 수 있는지 판단하고, 가능하다면 막대의 양 끝을 맞바꾸는 작업이 최소 몇 번 필요한지 구하여라.

첫째 줄에 모빌에 있는 막대의 수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 100000$). 막대에는 1번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $n$개의 줄 중 $i$번째 줄에는 $i$번 막대의 연결 정보가 두 정수 $l$과 $r$로 주어지며, 두 수는 공백 하나로 구분된다. $l$과 $r$은 각각 막대의 왼쪽 끝과 오른쪽 끝에 무엇이 매달려 있는지를 나타낸다. 장난감이 매달려 있으면 그 값은 $-1$이고, 다른 막대가 매달려 있으면 그 막대의 번호가 주어진다.

$i$번 막대 아래에 다른 막대가 매달려 있다면 그 막대의 번호는 항상 $i$보다 크다. 모빌의 맨 위에 있는 막대는 항상 1번이다.

Ike가 좋아하는 형태로 모빌을 바꾸는 데 필요한, 막대의 양 끝을 맞바꾸는 작업의 최소 횟수를 정수 하나로 출력한다. 만약 그런 형태로 바꾸는 것이 불가능하면 $-1$을 출력한다.

각 막대는 정확히 두 개의 자식을 가지므로 모빌 전체는 이진 트리로 볼 수 있다. 막대의 양 끝을 맞바꾸는 것은 그 막대의 왼쪽 서브트리와 오른쪽 서브트리를 통째로 교환하는 것과 같다. 각 막대의 번호가 그 자식 막대의 번호보다 작으므로, 번호가 큰 막대부터 처리하면 재귀 없이 아래에서 위로 계산할 수 있다.