구간 트리

Rikka에게는 내부 노드 $(n-1)$개와 리프 $n$개로 이루어진 구간 트리가 있다. 각 노드에는 공집합이 아닌 정수 구간이 하나씩 대응한다. 루트에는 $[1, n]$이 대응한다.

구간 $[l, r]$이 대응하는 내부 노드에 대해, $l \le m < r$을 만족하는 정수 $m$이 존재하여 왼쪽 자식에는 $[l, m]$, 오른쪽 자식에는 $[m+1, r]$이 대응한다.

처음에는 모든 노드가 흰색이다. Rikka는 구간에 대해 질의를 수행할 수 있다. 구간 $[A, B]$에 대한 질의에서는 다음 두 조건을 모두 만족하는 노드 $u$마다 루트에서 $u$까지의 경로($u$ 포함)를 검은색으로 칠한다.

• $u$의 구간 $[l, r]$이 $[A, B]$에 완전히 포함된다 ($A \le l \le r \le B$).
• $u$가 루트이거나, $u$의 부모 구간이 $[A, B]$에 완전히 포함되지 않는다.

모든 노드의 최종 색이 주어진다. 이 색을 만드는 데 필요한 질의 횟수의 최솟값을 구하라.

첫 줄에 정수 $n$ ($1 \le n \le 4000$)이 주어진다.

이어지는 $(2n-1)$개의 줄에 노드가 앞 순서(전위 순회)로 주어진다. 루트가 가장 먼저 나오고, 내부 노드 뒤에 왼쪽 서브트리, 이어서 오른쪽 서브트리가 온다.

내부 노드는 한 줄에 정수 $t_i$와 $m_i$ 두 개가, 리프는 정수 $t_i$ 하나가 주어진다. $t_i = 1$이면 검은색, $t_i = 0$이면 흰색이다. 입력은 항상 올바른 구간 트리를 나타낸다.

주어진 색을 만드는 데 필요한 질의 횟수의 최솟값을 한 정수로 출력한다. 주어진 색을 만들 수 없으면 OwO를 출력한다.