아레나

Bajtek은 부모님께 명절 선물로 최신 컴퓨터 게임 Byte Defence 4를 받았다. 열혈 게이머인 그는 곧장 CD를 넣고 게임을 시작했다. 게임에서는 Bajtonator라는 캐릭터를 조종해 경험치를 쌓고, 퀘스트를 수행하고, 점점 더 좋은 장비를 얻는다. 맵에는 값진 아이템을 얻을 수 있는 특수 아레나가 $n$개 있다. 아레나에 들어가려면 그 아레나 전용 입장권이 있어야 한다. Bajtek은 아레나와 입장권 체계를 자세히 살펴보기로 했다.

아레나는 전투가 벌어지는 곳이다. 플레이어가 입장권을 가지고 있으면 아레나에 들어가 그곳의 몬스터와 싸울 수 있다. 아레나에 들어간다고 입장권이 사라지지는 않는다. 몬스터는 플레이어가 아레나를 떠나면 다시 나타난다. 따라서 같은 입장권으로 같은 아레나에 여러 번 들어갈 수 있다. 몬스터를 물리친 플레이어는 드문 아이템과 함께 새 입장권을 받는다.

새 입장권은 그 아레나의 입장권 풀에서 무작위로 뽑힌다. 각 아레나의 풀은 공개되어 있어 Bajtek도 그 내용을 안다. 승리하면 풀에서 입장권 하나를 뽑고, 그 입장권의 사본을 플레이어에게 준다. 입장권 풀은 바뀌지 않으며, 풀에서 입장권이 줄어들지도 않는다. 따라서 여러 번 이기면 같은 입장권을 여러 장 갖게 될 수도 있다.

몬스터와의 전투도 쉽지 않다. Bajtek은 공략 글을 읽고 아레나 번호가 커질수록 난이도가 올라간다는 사실을 알게 되었다. 그래서 어떤 상수 $k$가 존재해, 번호가 $k$ 이하인 아레나에서는 문제없이 이길 수 있고, 번호가 $k$보다 큰 아레나에서는 절대 이길 수 없다고 판단했다.

Bajtek은 아이템에 끌려 아레나에서 싸우고 싶었지만 입장권이 하나도 없었다. 결국 실제 돈을 주고 입장권을 하나 사야 했다. 게임 시스템에 실망했지만 포기하지 않고 입장권 하나를 사기로 했다. 문제는 어떤 입장권을 살지였다. 그는 다른 아레나의 문도 열 수 있는 입장권을 원했다.

"A 아레나의 입장권을 하나만 사서 B 아레나에서 언젠가 반드시 이길 수 있다는 확신이 생긴다면, 그것도 나쁘지 않은 구매다." 소년은 이렇게 생각했다.

그래서 떠오른 질문은 이것이다. $k$가 정해졌을 때, 아레나 $A$의 입장권을 사면 Bajtek이 최적 전략으로 언젠가 아레나 $B$에 들어가 이길 수 있다고 확신할 수 있는 순서쌍 $(A, B)$ ($A \neq B$)는 몇 개인가? 얻는 입장권이 무엇이든 상관없이 성립해야 한다. 더 정확히는, 쌍 $(A, B)$마다 아레나를 고르는 전략과 유한한 상수 $M$이 존재해야 한다. 그 전략을 따르는 플레이어는 최대 $M$번 승리한 뒤에 아레나 $B$에서 승리를 강제할 수 있어야 한다. 그를 도와 모든 가능한 $k$ 값에 대해 이 개수를 구하라.

*전략은 형식적으로 게임 상태를 행동으로 옮기는 함수이지만, 지금 어떤 입장권을 가지고 있는지에 따라 지금 어느 아레나에서 싸워야 하는지를 알려 주는 결정 트리로 생각해도 된다.

첫 줄에 정수 $n$ ($2 \le n \le 2 \cdot 10^5$)이 주어진다. 이는 아레나의 개수이자 입장권 종류의 개수이기도 하다.

다음 $n$개 줄은 각 아레나의 입장권 풀을 설명한다. $i$번째 줄은 정수 $\ell_i$ ($1 \le \ell_i$)로 시작하며, 이는 $i$번째 풀에 있는 입장권의 개수다. 같은 줄에 $\ell_i$개의 정수가 이어지며, 이는 $i$번째 풀의 입장권으로 들어갈 수 있는 아레나 번호들이다. 아레나는 1부터 $n$까지 번호가 매겨진다.

한 입력 파일에서 모든 $\ell_i$의 합은 $5 \cdot 10^5$를 넘지 않는다.

한 줄에 정수 $n$개를 출력한다. $k$번째 정수는 아레나 $A$의 입장권을 사면, 플레이어가 싸울 수 있는 아레나가 번호 $k$ 이하인 곳뿐이라고 가정할 때 언젠가 아레나 $B$에서 승리할 수 있다고 확신할 수 있는 순서쌍 $(A, B)$ ($A \neq B$)의 개수이다.

$k = 9$인 경우(Bajtek이 모든 아레나에서 이길 수 있는 경우)를 보자. Bajtek이 아레나 1의 입장권을 사서 그곳에서 이기면, 아레나 2 또는 아레나 3의 입장권을 받는다. 아레나 3의 입장권을 받았다면 그곳에서 싸울 수 있고, 그러면 보상으로 아레나 2의 입장권을 반드시 받는다. 따라서 $(1, 2)$ 쌍은 올바르며 결과에 포함되어야 한다.

반대로 $k = 2$라면, 아레나 1의 입장권을 산 뒤 Bajtek은 아레나 3의 입장권을 받을 수 있는데, 그곳에서는 이길 수 없다. 따라서 $k = 2$일 때 $A = 1$인 쌍은 어느 것도 결과에 포함되지 않는다.

$k \ge 7$이고 Bajtek이 아레나 7의 입장권을 산다면($A = 7$), 그곳에서 몇 번을 이기든 아레나 4의 입장권만 계속 받거나 아레나 6의 입장권만 계속 받을 수 있다. 따라서 $(7, 4)$와 $(7, 6)$ 쌍은 어떤 $k$ 값에 대해서도 포함되지 않는다. 그러나 아레나 4의 입장권을 가지고 있든 아레나 6의 입장권을 가지고 있든, Bajtek은 그 아레나에 가서 아레나 5의 입장권을 얻을 수 있다. 따라서 $(7, 5)$ 쌍은 포함되어야 한다.

$k < 7$이고 Bajtek이 아레나 7의 입장권을 산다면, 그곳에서 기다리는 몬스터가 너무 강해 바로 막히게 된다.

$k = 9$일 때 올바른 쌍은 $(1, 2)$, $(2, 1)$, $(3, 1)$, $(3, 2)$, $(4, 5)$, $(6, 5)$, $(7, 5)$이다.