트리 곱

루트가 있는 트리 $T_1,T_2,\ldots,T_n$이 $n$개 주어진다. 순열 $p_1,p_2,\dots,p_n$과 $q_1,q_2,\ldots,q_n$을 구하라. $T_{p_1} \times T_{p_2} \times \ldots \times T_{p_n}$의 지름은 최대이고, $T_{q_1} \times T_{q_2} \times \ldots \times T_{q_n}$의 지름은 최소여야 한다.

루트가 있는 트리 $A$와 $B$에 대해 트리 곱 $T = A \times B$는 다음과 같이 정의한다. 트리 $A$를 복사한다. 그다음 $A$의 각 정점 $x$마다 $B$의 복사본을 만들고, $B$의 루트를 $x$와 합친다. 예시는 아래 표를 참고하라.

트리 곱은 결합법칙을 만족한다. $(A \times B) \times C = A \times (B \times C)$이다. 따라서 트리 3개 이상의 곱에서는 괄호를 생략할 수 있다.

다음을 기억하자.

• 트리는 사이클이 없는 연결 그래프이다. 루트가 있는 트리에는 루트라고 부르는 특별한 정점이 하나 있다. 정점 $v$의 부모는 루트에서 $v$까지의 경로에서 $v$와 다른 마지막 정점이다.
• 루트가 있는 트리의 지름은 트리에서 가장 긴 단순 경로의 길이이다. 경로의 길이는 경로에 포함된 간선의 수이다.

테스트 케이스는 여러 개이다. 입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 루트가 있는 트리의 개수 $n$ $(1 \le n \le 10^6)$이 주어진다.

이후 $n$개의 줄 각각은 정수 $m_i$ $(1 \le m_i \le 10^5)$로 시작하며, 이는 $i$번째 트리의 정점 수이다. 같은 줄에 정수 $p_{i,1},p_{i,2},\ldots,p_{i,m_i}$ $(0 \le p_{i,j} \le m_i)$가 이어서 주어지며, $j$번째 값은 $j$번째 정점의 부모이다. 트리의 루트는 부모로 $0$을 가진다.

모든 테스트 케이스에 걸쳐 $m_i$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 최대 지름과 최소 지름을 이 순서대로 두 정수로 출력한다.

첫 번째 예제에서 $T_1 \times T_2 \times T_3$이 최대 지름을 주고, $T_3 \times T_2 \times T_1$이 최소 지름을 준다.