C - Strong Surname 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

異なる名字を持つ N 人の人がおり、i 番目の人の名字はパラメータ (X_i,Y_i,Z_i) を持っています。異なる名字が同一のパラメータを持つこともあります。 今から N - 1 回、以下のことが起こります。

  • ある二人が親となり、その子供が一人出現する。親の二人は亡くなる。子供は、両親の名字のうち強い方を選んで自分の名字とする。パラメータ (x_1,y_1,z_1) を持つ名字がパラメータ (x_2,y_2,z_2) を持つ名字よりも強いとは、x_1 > x_2 かつ y_1 > y_2 かつ z_1 > z_2 を満たすことである。親の名字に強弱が付けられないとき、子供は名字を両親の名字からランダムに選ぶ。

N 人のうち、その人の名字が最後の一人の名字となりうる人の数を求めて下さい。

T 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

制約

  • 1 \le T \le 2 \times 10^5
  • 2 \le N \le 2 \times 10^5
  • 1 \le X_i, Y_i, Z_i \le N
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

出力

T 行出力せよ。

i 行目には、 i 番目のテストケースについて、その人の名字が最後の一人の名字となりうる人の数を出力せよ。

入力例 1

3
4
3 4 4
2 2 2
4 3 3
1 1 1
3
2 1 1
1 2 1
1 1 2
3
2 2 2
2 2 2
1 1 1

出力例 1

2
3
2

1 つ目のテストケースについては、例えば以下のようにイベントが起こることが考えられます。

i 番目の人の名字を名字 i と呼ぶことにする。

  • 名字 2 と名字 4 の人が親になる。名字 2 の方が強いため、子は名字 2 を持つ。
  • 名字 2 と名字 3 の人が親になる。名字 3 の方が強いため、子は名字 3 を持つ。
  • 名字 1 と名字 3 の人が親になる。名字 1 と名字 3 では強弱が付けられないため、子は名字 1 と 3 のいずれかを選ぶ。

名字 2 や名字 4 が最後の一人の名字になることはないため、答えは 2 になります。

Score : 600 points

Problem Statement

There are N people with distinct surnames, and the surname of the i-th person has parameters (X_i, Y_i, Z_i). Different surnames may have identical parameters. The following event occurs N - 1 times.

  • Two people become parents and one child appears. The two parents die. The child chooses the stronger of the two parents' surnames as their own. A surname with parameters (x_1, y_1, z_1) is stronger than a surname with parameters (x_2, y_2, z_2) if x_1 > x_2, y_1 > y_2, and z_1 > z_2 all hold. If neither parent's surname is stronger than the other's, the child randomly chooses one of the two parents' surnames.

Find the number of people among the N people whose surname can be the surname of the last remaining person.

You are given T test cases; solve each one.

Constraints

  • 1 \le T \le 2 \times 10^5
  • 2 \le N \le 2 \times 10^5
  • 1 \le X_i, Y_i, Z_i \le N
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

Output

Output T lines.

The i-th line should contain the number of people whose surname can be the surname of the last remaining person for the i-th test case.

Sample Input 1

3
4
3 4 4
2 2 2
4 3 3
1 1 1
3
2 1 1
1 2 1
1 1 2
3
2 2 2
2 2 2
1 1 1

Sample Output 1

2
3
2

For the first test case, below is a possible sequence of events.

Let surname i denote the surname of the i-th person.

  • The people with surnames 2 and 4 become parents. Surname 2 is stronger, so the child has surname 2.
  • The people with surnames 2 and 3 become parents. Surname 3 is stronger, so the child has surname 3.
  • The people with surnames 1 and 3 become parents. Neither surname 1 nor surname 3 is stronger than the other, so the child chooses either surname 1 or 3.

Neither surname 2 nor surname 4 can be the surname of the last remaining person, so the answer is 2.