Famous
Турнир за Купата на Декана, 2011
Time Limit: 0.2s, Memory Limit: 64MiB
В училището на Ели има N ученика. Както във всяко училище, там има хора, които са популярни и такива, които не са. За да стане един човек известен, най-често той трябва да комуникира с достатъчно на брой други известни хора. Ели е решила да научи кои са всички известни нейни връстници в училище, като следи тяхната кореспонденция (e-mail-и, twitter, съобщения във Facebook, SMS-и). Как тя успява да прави това не ни засяга пряко.
Тъй като трафикът е сравнително голям, тя е решила да автоматизира процеса. Като цяло, ако някой непопулярен ученик е разменил поне едно съобщение с K или повече на брой от популярните, той вече също се счита за популярен. За съжаление, системата за следене на Ели е малко бъгава, затова за всяко съобщение тя знае единствено между кои двама души е било изпратено, но не и кога точно е станало това.
Знаейки кои са били известните хора преди изпращането на първото съобщение, помогнете на Ели да намери колко най-много (и кои) ученици биха могли да бъдат известни след разменянето на всички съобщения.
Тъй като трафикът е сравнително голям, тя е решила да автоматизира процеса. Като цяло, ако някой непопулярен ученик е разменил поне едно съобщение с K или повече на брой от популярните, той вече също се счита за популярен. За съжаление, системата за следене на Ели е малко бъгава, затова за всяко съобщение тя знае единствено между кои двама души е било изпратено, но не и кога точно е станало това.
Знаейки кои са били известните хора преди изпращането на първото съобщение, помогнете на Ели да намери колко най-много (и кои) ученици биха могли да бъдат известни след разменянето на всички съобщения.
Вход
На първия ред на стандартния вход ще бъдат зададени четири цели числа N, K, F, и M – съответно броя ученици в училището, броя известни хора, с които трябва да си комуникира даден човек за да стане също известен, броя първоначално известни хора и броя разменени съобщения. На следващия ред ще има F стринга, задаващи имената на първоначално-известните хора. На всеки от следващите M реда ще бъде зададена по една двойка стрингове - имената на двама ученика, които са си разменили съобщение. Считаме, че комуникацията е двупосочна. Гарантирано е, че няма да има съобщение, изпратено от ученик до себе си. Както казахме, редът, в който са дадени съобщенията на входа, може да не отговаря на реда, в който са били изпратени те. Всички имена във входа ще са съставени от главни и малки латински букви и ще бъдат не по-дълги от 10 символа.
Изход
На стандартния изход изведете ред с имената на известните хора накрая, ако считаме, че съобщенията са били разменени в реда, в който най-много хора биха станали известни. Изведете имената разделени с по един интервал, сортирани в лексикографски ред. Ако има повече от един възможен отговор, изведете който и да е от тях.
Ограничения
- 1 ≤ N ≤ 1,000
- 1 ≤ M ≤ 10,000
- 1 ≤ F, K ≤ N
| Примерен Вход | Примерен Изход |
|---|---|
| 9 2 3 6 Stancho Elly Rumen Kriss Pesho Elly Ani Elly Kriss Kriss Stancho Elly Pesho Stancho Pancho | Elly Kriss Pesho Rumen Stancho |
В училището има девет човека, като в началото известни са Stancho, Elly, и Rumen. За да стане известен някой трябва да си комуникира с поне двама вече известни. В една от възможните оптимални последователности първо Stancho и Elly комуникират с Kriss, правейки я известна. След товa тя и Elly могат да комуникират с Pesho, като също го правят известен. Забележете, че ако Крис беше комуникирала с Пешо преди да стане известна, то той нямаше да стане известен. Pancho така и не става известен, тъй като комуникира само с един от известните ученици. В училището има и двама души, които нито са били известни, нито са си комуникирали с когото и да било.