問題一覧 > 通常問題

No.812 Change of Class

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

問題文

はむへいくんの新しいクラスには$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

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