有一種奇怪的病毒在世界蔓延，
科學家觀察以後發現該病毒具有以下特徵：
1. 病毒具有衰變性，從最開始的帶原者由內而外，最多只會往外傳播 K 層，就不會再傳播給下個人
2. 病毒可能發生變異，變異只會發生在傳播開始前，而不會發生在傳播過程中，病毒編號越大代表是越新變異的病毒
3. 曾感染過的患者會帶有抗體，除非遇到更新型變異株，否則該抗體可以抵禦相同或較舊版本病毒的攻擊
以下圖為例，
假設每次從帶原者開始最多只能往外傳播 2 層。
首先(成員1)為(病毒10)的帶原者，並將(病毒10)往外傳播，即往外傳播給(成員0、3、5)
接著(成員2)為(病毒20)的帶原者，並將(病毒20)往外傳播，即往外傳播給(成員4、3、8)
其中特別的是，(成員3)雖然已有(病毒10)的抗體，但因(病毒20)為更新型病毒(數字越大代表越新)，舊的抗體不足以抵抗，仍會染疫
最後(成員7)為(病毒15)的帶原者，並將(病毒15)往外傳播，即往外傳播給(成員6、5)
其中特別的是，(成員3、8)雖然也在兩層傳播的範圍內，但因已具有更新型的(病毒20)抗體，因此不會染疫；
(成員5)則因抗體較舊，因此仍會染疫
給定人際網絡關係，與依照發生時間由前至後所觀察到的病毒帶原事件。
請計算每次事件的感染威力，即於該次事件傳播結束時，會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)。
其中你可以假設每次觀察到的病毒帶原事件，
都會在上次帶原事件傳播結束後才發生，也就是不會有兩事件同時在傳播，以致互相干擾的狀況。
並且每次病毒帶原事件的源頭都是合理的，
也就是不會有已於先前發生事件得到新型抗體，但仍成為後來發生事件舊病毒最初帶原者的狀況。
第一行有四個正整數 N, M, K, Q，
代表總人數、關聯個數、最大傳遞層數、發生的帶原事件數
1 ≤ N ≤ 1000
1 ≤ M ≤ N*(N-1)/2
1 ≤ K, Q ≤ 10
接著有 M 行，每行有兩個整數 u 和 v，
代表成員 u 和成員 v 雙向相連
0 ≤ u < v ≤ N-1
最後有 Q 行，代表由先至後所觀察到的事件。
對於每個事件有兩個整數 a 和 b，
代表於該次事件中成員 a 為病毒編號 b 的最初帶原者
0 ≤ a ≤ N-1
1 ≤ b ≤ 109
其中保證所有輸入的 b 值皆不相同，
且 b 編號越大代表為越新型變異株
印出 Q 行
每行為該次事件的感染威力，
即於該次事件傳播結束時，會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)
9 10 2 3 0 1 0 3 0 5 2 4 3 4 3 6 4 8 5 6 6 7 6 8 1 10 2 20 7 15
4 4 3
4 4 2 1 0 1 0 2 1 2 2 3 0 99999
4
公開 測資點#0 (5%): 2.0s , <1M
公開 測資點#1 (5%): 2.0s , <1M
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
10%：K = 1
30%：Q = 1
60%：無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 35251 | mushroom.cs9 ... (mushroom) | k573 | 258 | 2023-05-19 02:38 |