진화

여러 생명체들을 대상으로 진화 과정을 다루는 연구를 진행하려고 한다. 최초 생명체를 제외한 모든 다른 생명체들은 기존에 존재하던 생명체가 진화하면서 새롭게 탄생하게 된다. 이 때, 기존에 존재하던 생명체를 부모 생명체, 새롭게 탄생한 생명체를 자식 생명체라고 정의한다. 

생명체들이 진화를 통해 탄생하는 과정은 생명체들을 정점, 진화 과정을 부모 생명체와 자식 생명체를 잇는 간선으로 나타내 최초 생명체를 루트로 한 트리 구조로 표현할 수 있다. 예를 들어, 아래 그림은 1번 생명체가 진화해 2, 3번 생명체가 탄생하고, 2번 생명체가 진화해 4, 5, 6번 생명체가 탄생하며, 3번 생명체가 진화해 7번 생명체가 탄생하며 6번 생명체가 진화해 8, 9번 생명체가 탄생하는 과정을 1번 생명체를 루트로 한 트리 구조로 표현한 것이다. 이러한 트리를 진화 트리라고 부르자.

자식 진화체가 존재하는 생명체 각각에 대해, 가능한 진화 방법들 중 하나의 진화 방법을 집중적으로 분석할 주요 진화, 나머지 진화 방법들을 부가 진화로 분류하려고 한다.

이러한 분류 방법의 효율성은 진화 복잡도를 측정하여 구할 수 있다. 두 생명체 A와 B 간의 진화 복잡도는 진화 트리에서 생명체 A와 B를 잇는 단순 경로 상에서 지나는 \underline{부가 진화}의 개수로 정의한다. 진화 트리의 진화 복잡도는 모든 생명체 쌍에 대한 진화 복잡도의 최댓값으로 정의한다. 

진화 복잡도가 커질수록 두 생명체들간의 연관성을 분석하기가 어려워지기에, 진화 트리의 진화 복잡도가 낮을수록 효율적인 방식이다. 따라서, 적절히 주요 진화와 부가 진화로 분류하여 진화 트리의 진화 복잡도를 최소화해야 한다.

$N+Q$일동안 연구를 진행한다. 연구를 진행하는 첫 날에는 1번 생명체의 발견만이 이루어져 있으며, 각 날에는 다음의 두 가지 연구 중 하나를 진행한다.

• 기존에 발견된 생명체에서 진화하여 탄생하는 새로운 생명체를 발견한다. 기존에 발견된 생명체의 수가 $T$였다면, 이 생명체는 $T+1$번 생명체로 명명한다. 이 연구는 $N$번 일어난다.
• 한 생명체에 대해, 해당 생명체에서 0번 이상의 진화를 거쳐 탄생하는 생명체들을 분석한다. 해당 생명체를 최초 생명체로 두어 만들어지는 진화 트리에 대해, 진화 트리의 진화 복잡도의 최솟값을 구해야 한다. 각 분석은 독립적이며, 이 분석에서 분류한 방법이 나중의 분석들에 영향을 미치지 않는다는 점에 유의하라. 이 연구는 $Q$번 일어난다.

해당 연구 계획을 진행하는 프로그램을 작성하여라.

• $1 \le N \le 500\\,000$
• $1 \le Q \le 500\\,000$