問題一覧 > 通常問題

No.812 Change of Class

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 169
作問者 : hamuhei4869 / テスター : koba-e964
18 ProblemId : 2850 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-03-30 18:29:23

問題文

はむへいくんの新しいクラスには1∼Nで表されるN人が所属しています。このクラス内の既存の友好関係は以下のようなM個の情報によって表現されます。


  • piさんとqiさんは友達である。(1≦i≦M)

このクラスでは1日が経過するたびに友好関係が以下のように変化します。

  • まだ友達でないような人のペア(a,b)を考える。aさんともbさんとも友達である人が存在するとき、その日が終わるとaさんとbさんは友達になる。
  • 友達の関係が解消されることはない。

Q人の名前が呼ばれます。
i番目に名前が呼ばれた人をAiとするとき、
各i(1≦i≦Q)について、Aiさんが友達になれる最大の人数を答えてください。また、その人数は初日を0日目として何日目に達成できるかも同時に答えてください。

入力

N M
p1q1
.
.
.
pMqM
Q
A1
.
.
.
AQ

1≦N≦105
0≦M≦min((N∗(N−1))/2,105)

i(1≦i≦M)について
1≦pi<qi≦N

i≠jなら
(pi,qi)≠(pj,qj)

1≦Q≦30
1≦Ai≦N(1≦i≦Q)

出力

答えをQ行出力してください。i行目にはi人目(Ai)の答えを出力してください。
具体的にはi行目には
i番目の人Aiが友達にできる最大の人数、その人数が初日を0日目として何日目に達成できるかを空白区切りに出力してください。

サンプル

サンプル1
入力
2 1
1 2
2
1
2
出力
1 0
1 0

既存の状態で1と2は友達であり、互いにこれ以上友達を増やすことはできません。

サンプル2
入力
5 3
1 2
2 3
3 4
5
1
2
3
4
5
出力
3 2
3 1
3 1
3 2
0 0

誰とも友達になれない人がいる場合があることに注意してください。

サンプル3
入力
18 13
1 2
3 4
4 5
6 7
7 8
8 9
9 10
11 12
12 13
13 14
14 15
15 16
16 17
4
1
3
6
11
出力
1 0
2 1
4 2
6 3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。