B - 購入
Milk
2
s
1024
MB
200
点
問題文
メルカリには、ユーザー $1$ からユーザー $10^{9}$ までの $10^{9}$ 人のユーザーがいます。また、メルカリには、商品 $1$ から商品 $10^{9}$ までの $10^{9}$ 個の商品が $1$ つずつ出品されています。
はじめ、すべてのユーザーの幸福度は $0$ です。
次のような形式の情報が $N$ 個与えられます。$i$ 番目の情報は以下の通りです。
- ユーザー $u_i$ が商品 $v_i$ を購入すると、そのユーザーの幸福度が $h_i$ 上昇する。
ユーザーが $N$ 個の情報にない方法で商品を購入することはできません。すべてのユーザーの幸福度の合計が最大となるような購入方法を求めてください。
購入方法とは、商品 $v_j$ がユーザー $u_j$ によって購入されることを表す情報 $(v_j, u_j)$ の集合です。ただし、 $1$ つの商品は一度のみ購入することができます。
なお、与えられる入力では、幸福度の合計が最大となる購入方法が一意に定まることが保証されています。
制約
- $1 \leq N \leq 50{,}000$
- $1 \leq u_i \leq 10^{9}$
- $1 \leq v_i \leq 10^{9}$
- $1 \leq h_i \leq 100$
- $i \neq j$ のとき、$(u_i, v_i) \neq (u_j, v_j)$
- $i \neq j$ かつ $v_i = v_j$ のとき、$h_i \neq h_j$
- 入力はすべて整数
入力
入力は以下の形式で与えられる。
$N$
$u_1$ $v_1$ $h_1$
$u_2$ $v_2$ $h_2$
$\dots$
$u_N$ $v_N$ $h_N$
出力
一行目に、幸福度の合計が最大となるような購入数 $M$ を出力してください。
続く二行目から $M+1$ 行目には、商品 $v_i$ がユーザ $u_i$ に購入されることを表す $v_i$ と $u_i$ を空白区切りで出力してください。
このとき、出力は $v_i$ が昇順になるようにしてください。
$M$
$v_1$ $u_1$
$v_2$ $u_2$
$\dots$
$v_M$ $u_M$
入力例 1
4
2 2 6
1 1 37
3 1 40
1 2 56
出力例 1
2
1 3
2 1
ユーザー $3$ が商品 $1$ を購入し、ユーザー $1$ が商品 $2$ を購入した場合、合計幸福度が最大 $(56 + 40 = 96)$ になります。
出力の形式に注意してください。
入力例 2
10
3 5 82
2 5 62
4 5 34
1 5 2
1 4 91
4 3 32
3 1 25
5 2 31
4 1 11
5 3 70
出力例 2
5
1 3
2 5
3 5
4 1
5 3
入力例 3
15
4 20 71
10 10 57
2 20 50
6 19 31
5 6 25
3 2 79
5 16 9
2 5 20
1 3 90
9 13 91
9 9 67
4 7 87
10 14 75
5 15 64
6 3 42
出力例 3
13
2 3
3 1
5 2
6 5
7 4
9 9
10 10
13 9
14 10
15 5
16 5
19 6
20 4