Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kaimynų kaimynai

Duotas besvoris neorientuotas grafas. Viršūnės u ir v yra vadinamos kaimynėmis, jei jas jungia briauna. Viršūnės u ir v vadinamos antros eilės kaimynėmis, jei galioja šios sąlygos: u ir v nėra ta pati viršūnė; u ir v nėra kaimynės; bei egzistuoja tokia viršūnė w, kad u ir w būtų kaimynės bei w ir v būtų kaimynės.

Žemiau pateiktame grafe viršūnės A kaimynės yra B, C ir D, o antros eilės kaimynės yra E, F, G ir H.

Pavyzdys

Jūsų užduotis - rasti visas tam tikros viršūnės antros eilės kaimynes.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m - grafo viršūnių ir briaunų kiekiai (1\\leqn,m\\leq10^5).

Antroje eilutėje pateikta n tarpais atskirtų simbolių eilučių. i-oji simbolių eilutė p_i žymi i-osios viršūnės pavadinimą. Pavadinimų ilgiai neviršija 10 simbolių, juos sudaro tik didžiosios ir mažosios lotyniškos abėcėlės raidės.

Toliau pateikta m eilučių. i-ojoje iš jų yra dvi tarpu atskirtos simbolių eilutės u_i ir v_i, nurodančios, kad tarp viršūnių su pavadinimais u_i ir v_i yra briauna. Yra garantuota, kad nebus pasikartojančių briaunų ir kilpų.

Paskutinėje eilutėje pateiktas viena simbolių eilutė s - viršūnės, kurios antros eilės kaimynių ieškosime, pavadinimas.

Rezultatai

Jūsų programa turi išvesti dvi eilutes. Pirmoje eilutėje turi būti vienas sveikasis skaičius k - viršūnės s antros eilės kaimynių kiekis.

Antroje eilutėje turi būti k tarpais atskirtų simbolių eilučių - viršūnės s antros eilės kaimynių pavadinimai. Šie pavadinimai turi būti išrikiuoti abėcėlės tvarka.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
11 12
A B C D E F G H I J K
A B
A C
A D
B C
B E
B F
D F
D G
D H
E I
F J
F K
A
 
4
E F G H
 Šis pavyzdys atitinka sąlygoje parodytą grafą. 
10 12
sarunas raminta nojus ramunas mykolas beta arturas zuzana julius ina
mykolas zuzana
mykolas ramunas
ramunas zuzana
ramunas beta
zuzana beta
ramunas arturas
zuzana nojus
beta sarunas
sarunas raminta
nojus sarunas
ramunas raminta
julius ina
mykolas
 
4
arturas beta nojus raminta
 Pradiniuose duomenys aprašytas grafas atrodo taip: Paaiškinimas Viršūnės "mykolas" antros eilės kaimynės nuspalvintos raudonai.