자운의 열차

잠시 자운이 필트오버로부터 독립했다고 가정해 봅시다. 산업 단지에 가까운 지역인 만큼, 자운에서는 무엇보다 생산 거점들 사이를 빠르게 잇는 교통망이 중요합니다.

자운에 철도 노선 $n$개를 차례로 건설하는 계획이 세워졌습니다. 먼저 첫 번째 노선이 개통되고, 얼마 뒤 두 번째 노선이 개통되며, 이런 식으로 이어집니다. 노선끼리는 교차할 수 있고, 여러 번 교차할 수도 있습니다. $i$번째 노선과 $j$번째 노선이 교차하는 지점에서는 교통이 $i$번째 노선에서 $j$번째 노선으로, 또는 그 반대로 옮겨 탈 수 있습니다.

$i$번째 노선이 건설되면, 낮 동안 그 노선에는 정확히 $a_i$대의 열차가 운행합니다. 밤이 되면 지역의 활동이 멈추고, 모든 열차는 차고지에 있어야 합니다(반드시 자신의 노선에 있는 차고지일 필요는 없습니다). 수용량이 $A$인 차고지에는 최대 $A$대의 열차를 넣을 수 있습니다. 각 열차는 도달 가능한 차고지 중 어디에든 배치할 수 있습니다. 즉, 노선 $j$의 차고지에 자리가 있고 노선 $i$와 $j$가 교차한다면, 낮에 노선 $i$를 운행하는 열차는 밤에 노선 $j$의 차고지에 머물 수 있습니다.

노선이 공식적으로 개통되기 전이라면, 어떤 노선에든 원하는 수용량의 차고지를 원하는 만큼 지을 수 있습니다. 목표는 어느 시점에서든 개통된 노선의 모든 열차를 도달 가능한 차고지에 배치할 수 있도록 하는 것입니다. 차고지 건설에는 큰 비용이 들기 때문에, 전체 수용량을 최소화하고, 전체 수용량이 같다면 차고지 개수도 최소화하려고 합니다.

계획된 순서대로 노선을 개통하는 데 필요한 차고지 중, 전체 수용량이 최소이면서 개수도 최소인 경우의 차고지 개수 $k$를 구하세요. $k$개의 차고지 각각에 대해, 어느 노선에 건설해야 하는지와 수용량을 출력하세요. 전체 수용량을 먼저 최소화해야 하며, 그 다음에 차고지 개수를 최소화해야 합니다.

첫 줄에는 건설할 노선의 수를 나타내는 정수 $n$이 주어집니다($1 \leqslant n \leqslant 10^6$).

다음 $2 \cdot n$개의 줄에는 아래 형식의 질의가 주어집니다.

$i$번째 노선의 설명 첫 줄에는 그 노선을 운행하는 열차 수를 나타내는 정수 $a_i$가 하나 주어집니다($1 \leqslant a_i \leqslant 10^6$). 둘째 줄에는 먼저 $i$번째 노선이 교차하는, 이미 건설된 노선의 수 $c_i$가 주어지고($0 \leqslant c_i \leqslant 2 \cdot 10^6$), 이어서 그 노선들의 번호가 공백으로 구분되어 $c_i$개 주어집니다. 나열된 모든 $t$에 대해 $1 \leqslant t < i$가 보장됩니다.

모든 $i$에 대한 $c_i$의 합은 $2 \cdot 10^6$을 넘지 않는다고 보장됩니다.

첫 줄에 건설할 차고지의 개수 $k$를 출력합니다. 다음 $k$개의 줄에는 각각 공백으로 구분된 두 정수를 출력합니다. 첫 번째 정수는 차고지를 건설할 노선 번호($1$ 이상 $n$ 이하)이고, 두 번째 정수는 그 차고지의 수용량입니다.