No.812 Change of Class

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 93
作問者 : hamuhei4869hamuhei4869 / テスター : koba-e964koba-e964
7 ProblemId : 2850 / 出題時の順位表

問題文

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


  • $p_i$さんと$q_i$さんは友達である。$(1 \leqq i \leqq M)$

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

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

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

入力

$N\ M$
$p_1 q_1$
.
.
.
$p_M q_M$
$Q$
$A_1$
.
.
.
$A_Q$

$1 \leqq N \leqq 10^5$
$0 \leqq M \leqq \min((N * (N-1))/2, 10^5)$

$i(1 \leqq i \leqq M)$について
$1 \leqq p_i < q_i \leqq N$

$i \neq j$なら
$(p_i, q_i) \neq (p_j, q_j)$

$1 \leqq Q \leqq 30$
$1 \leqq A_i \leqq N (1 \leqq i \leqq Q)$

出力

答えを$Q$行出力してください。$i$行目には$i$人目$(A_i)$の答えを出力してください。
具体的には$i$行目には
$i$番目の人$A_i$が友達にできる最大の人数、その人数が初日を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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。