以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 2 – Making Friends on Joitter is Fun
ジョイッターで友だちをつくろう(Making Friends on Joitter is Fun)
ジョイッター(Joitter) は,短い日記の気軽な投稿や写真の共有を通して,知り合いとのインターネット上
でのコミュニケーションをより快適にする,話題沸騰中のソーシャル・ネットワーキング・サービス(SNS)
である.
ジョイッターでは,自分以外のユーザをフォローすることができる.あるユーザa がある他のユーザb を
フォローすると,ユーザa のアカウントからユーザb の発言を閲覧することができるようになる.このと
き,ユーザb がユーザa をフォローすることも,しないことも可能である.ただし,自分自身をフォローし
たり,あるユーザa がユーザb を2 回以上フォローすることはできない.
今,人1, 2, . . . , N からなるN 人のユーザがJoitter に新規登録した.現時点ではどのユーザも他のユーザ
を誰もフォローしていない.
N 人は仲良くなるために,これからM 日間にわたり,1 日1 回ずつあるユーザが別のユーザをフォロー
することにした.i 日目(1 ≦i ≦M) には,人Ai が人Bi を新たにフォローする.
Joitter では,ユーザ間のフォローを増やすため,M 日間のうちのある1 回,サービス内で交流イベント
を開催しようと計画している.交流イベントは,以下のようにして行われる.
1. N 人のユーザのうち1 人(以下,人x と呼ぶことにする) を選ぶ.
2. 人x が現在フォローしているユーザのうち1 人(以下,人y と呼ぶことにする) を選ぶ.
3. 人x が現在フォローしておらず,人y が現在フォローしている人x 以外のユーザで,そのユーザも人
y を現在フォローしているもののうち1 人(以下,人z と呼ぶことにする) を選ぶ.
4. 人x が人z をフォローする.
5. 条件を満たす人x,人y,人z の組が選べなくなるまで以上を繰り返す.
交流イベントをいつ行うかはまだ決まっていない.そこで,M 日間の各日において,あるユーザが別の
ユーザをフォローした後に交流イベントを開催したとき,交流イベントが終了した直後にN 人がフォロー
している人数の合計の最大値を求めたい.ただし,交流イベントはその日のうちに終了するものとする.
ユーザの人数とM 日間のフォローの情報が与えられたとき,各日における交流イベントが終了した直後
のN 人がフォローしている人数の合計の最大値を求めるプログラムを作成せよ.
ジョイッターで友だちをつくろう– 1 / 4
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 2 – Making Friends on Joitter is Fun
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N M
A1 B1
...
AM BM
出力
M 行出力せよ.i 行目(1 ≦i ≦M) には,i 日目にあるユーザが別のユーザをフォローした後に交流イベ
ントを開催したとき,交流イベントが終了した直後にN 人がフォローしている人数の合計の最大値を出力
せよ.
制約
• 2 ≦N ≦100 000.
• 1 ≦M ≦300 000.
• 1 ≦Ai ≦N (1 ≦i ≦M).
• 1 ≦Bi ≦N (1 ≦i ≦M).
• Ai , Bi (1 ≦i ≦M).
• (Ai, Bi) , (Aj, Bj) (1 ≦i < j ≦M).
小課題
1. (1 点) N ≦50.
2. (16 点) N ≦2000.
3. (83 点) 追加の制限はない.
ジョイッターで友だちをつくろう– 2 / 4
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 2 – Making Friends on Joitter is Fun
入出力例
入力例1 出力例1
4 6 1
1 2 2
2 3 4
3 2 4
1 3 5
3 4 9
4 3
• 1 日目に人1 が人2 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ
ローすることはなく,フォロー人数の合計は1 である.
• 2 日目に人2 が人3 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ
ローすることはなく,フォロー人数の合計は2 である.
• 3 日目に人3 が人2 をフォローする.この後交流イベントを開くと,例えば人1 が人3 をフォローす
る.この場合フォロー人数の合計は4 となり,最大である.
• 4 日目に人1 が人3 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ
ローすることはなく,フォロー人数の合計は4 となる.
• 5 日目に人3 が人4 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ
ローすることはなく,フォロー人数の合計は5 となる.
• 6 日目に人4 が人3 をフォローする.この後交流イベントを開くと,例えば人1 が人4 をフォロー
し,人2 が人4 をフォローし,人4 が人2 をフォローする.この場合フォロー人数の合計は9 とな
り,最大である.
ジョイッターで友だちをつくろう– 3 / 4
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 2 – Making Friends on Joitter is Fun
入力例2 出力例2
6 10 1
1 2 2
2 3 3
3 4 4
4 5 5
5 6 7
6 5 11
5 4 17
4 3 25
3 2 30
2 1
ジョイッターで友だちをつくろう– 4 / 4