Informatica Online Judge

  래빗 하우스 [1940 / 0794]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (34tn 조현우)]
Writer ID : [gs16109]

Background

현우는 래빗 하우스에서 코코아와 카푸치노를 팔고 있다.
하지만 일을 하지 얼마 되지 않은 현우는 맛을 보지 않고서는 그것이 코코아인지 카푸치노인지 알지 못한다.
이를 보다 못한 경곽이는 코코아와 카푸치노를 총 n개 만들어서 현우에게 시험을 낼 예정이다.


다행히도 현우는 경곽이가 코코아와 카푸치노를 만드는 것을 몰래 훔쳐 보아 임의의 i,j(1<= i,j <= n)번째 컵에 대해 그 둘이 서로 같은 음료를 담고 있는지 다른 음료를 담고 있는지 알아내었다.
현우는 경곽이 몰래 각각의 컵에 "그 컵과 다른 종류의 음료를 담고 있는 컵의 번호"를 적기로 했다.
머리가 좋은 현우는 1 ~ n-1번째 컵에 하나씩만 번호를 적어도 된다는 것을 알아냈다.
이로써 현우는 한 번만 맛을 보는 것으로 1 ~ n번째 컵에 무엇이 담겨져 있는지 알아낼 수 있다!

하지만 경곽이는 한꺼번에 n개의 컵을 사용하지 않고, 그 중 a ~ b번째 컵만 시험에 사용할 계획이다.
현우는 당황했지만, 컵에 적힌 번호를 이용해 모두 맛을 보지 않고도 모든 음료의 종류를 알아낼 수 있다는 것을 깨달았다.
임의의 a, b에 대해서 현우가 최소한으로만 맛을 보고도 모든 음료의 종류를 알아낼 수 있도록 도와주자.

Input

첫째 줄에는 n과 m이 공백을 사이에 두고 주어진다. 이때, m은 주어지는 a, b 쌍의 개수이다.
둘째 줄부터 n-1줄에 걸쳐 1 ~ n-1번째 컵에 적힌 번호가 차례대로 입력된다.
이후 m개의 줄에 걸쳐 각각 a, b가 입력된다.

[입력값의 정의역]
1 <= n <= 2000
1 <= m <= 100000
1 <= a < b <= n

Output

각 a, b에 대해 현우가 a ~ b번째 컵에 무엇이 담겨 있는지 알기 위해 맛을 봐야 하는 최소한의 음료의 개수를 출력한다.

IO Example

입력
6 2
6
1
1
6
4
1 5
2 4

출럭
2
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]