Quş Müşahidəsi#9712

Quş Müşahidəsi

1 saniyə

128 meqabayt

Çətin

Kiyara qeyri-adi tərzdə hərəkət edən bir quş növünü öyrənir. Onların hərəkətlərini qraf dili ilə təsvir etmək daha rahatdır: istiqamətli $G$ qrafı mövcuddur, burada hər zirvə bir ağaca uyğundur və quş yalnız qraf $G$ -də $(T_{a}, T_{b})$ (T_a, T_b) qırağı varsa, $T_{a}$ T_a ağacından $T_{b}$ T_b ağacına uça bilər.

Kiyara quşların hərəkətlərini təsvir edən $G$ qrafının dəqiq formasını bilmir, lakin əvvəlki sahə müşahidələri zamanı bir çox quşun səyahətləri ilə bağlı məlumat toplamışdır. Bu məlumatlar əsasında o, quşların necə hərəkət etdiyini əks etdirən $P$ qrafını qurmuşdur. Kiyara quşların birbaşa $a$ -dan $b$ -ə uça biləcəyi halda, bu uçuşu ən azı bir dəfə müşahidə etdiyinə əmindir. Lakin mümkündür ki, quş əvvəlcə $a$ -dan $b$ -ə, sonra $c$ -yə uça bilmiş olsun, lakin Kiyara yalnız $a$ və $c$ nöqtələrini görüb, sonra $(a, c)$ qırağını $P$ qrafına əlavə etmiş olsun. Həmçinin mümkündür ki, quş $a \to b \to c \to d$ a \rightarrow b \rightarrow c \rightarrow d marşrutu uçmuş, ancaq Kiyara yalnız $a$ və $d$ -ni görərək, $P$ -yə $(a, d)$ əlavə etmiş olsun, və s. Ümumilikdə, Kiyara bilir ki, $P$ qrafı $G$ qrafının bütün qıraqlarını ehtiva edir və bəzi əlavə $(a, b)$ qıraqlarını da ehtiva edə bilər ki, burada $G$ qrafında $a$ -dan $b$ -yə bir yol mövcuddur (bu zaman $P$ bu cür qıraqların hamısını ehtiva etməyə məcbur deyil).

Növbəti sahə araşdırmasında Kiyara bazanı müəyyən bir $T$ ağacının yanında yerləşdirməyə qərar verdi. Quşların $T$ ağacına yaxınlaşmasını öncədən xəbərdar olmaq üçün, onlar yalnız qraf $G$ -də $(T^{'}, T)$ (T', T) qırağı varsa, quşlar oraya uça bilər (yəni belə ağaclar $T^{'}$ T' ki, $G$ qrafında $(T^{'}, T)$ (T', T) qırağı mövcuddur) və oraya detektorlar quraşdırmaq istəyir. Detektorlar bahalı olduğu üçün, Kiyara onları yalnız $G$ qrafının həqiqətində $(T^{'}, T)$ (T', T) qırağı olduğuna əmin olduğu ağaclara quraşdırmaq istəyir.

Giriş

Giriş məlumatları $P$ qrafını təsvir edir. Birinci sətir üç tam ədəd ehtiva edir: $N, M (1 \leq N, M \leq 1 0^{5})$ N, M~(1 \le N, M \le 10^5) və $T (0 \leq T < N)$ T~(0 \le T < N). Burada $N$ — $P$ qrafının zirvələrinin sayıdır, $M$ — $P$ qrafının qıraqlarının sayıdır və $T$ — Kiyarın bazasını yerləşdirəcəyi ağaca uyğun zirvədir.

Növbəti $M$ sətirlər $P$ qrafının qıraqlarını təsvir edir. Onların hər biri iki tam ədəd $a$ və $b$ ( $0 \leq a, b < N$ 0 \le a, b < N və $a \neq = b$ a \ne b) ehtiva edir ki, $(a, b) \in P$ (a, b) \in P. İşarə edilir ki, eyni cüt $(a, b)$ bir dəfədən artıq görünməyəcəkdir.

Çıxış

$S (T)$ cəmisini çıxarın. Birinci sətir $S (T)$ -də zirvələrin sayını göstərən bir tam ədəd $L$ ehtiva etməlidir, ardından $L$ sətirlərdə $S (T)$ cəminin hər bir elementi ayrı-ayrılıqda verilməlidir. $S (T)$ cəminin elementləri artan sırada çıxarılmalıdır, hər bir element ayrıca bir sətirdə veriləcəkdir.

Nümunələr

1-ci misal izahatı. Zirvə $1$ $S (2)$ -yə daxildir, çünki $1$ -dən $2$ -ə gedən (yeganə) yol $(1, 2)$ qırağını istifadə edir. Zirvə $0$ $S (2)$ -yə daxil deyil, çünki $0 \to 1 \to 2$ 0 \rightarrow 1 \rightarrow 2 yolu $(0, 2)$ qırağını istifadə etmir.

2-ci misal izahatı. 1-ci misal ilə eyni səbəbə görə, zirvə $0$ $S (2)$ -yə daxil deyil, amma zirvə $1$ daxildir. Zirvələr $3$ və $5$ $S (2)$ -yə daxil deyil, çünki qrafda $(3, 2)$ və ya $(5, 2)$ qıraqları yoxdur. Nəhayət, zirvə $4$ $S (2)$ -yə daxildir, çünki $4$ -dən $2$ -yə gedən bütün yollar $(4, 2)$ qırağını istifadə edir.

Nümunə 1

Nümunə 2