K — Sánta kutya

Donald és Mike a szabad világ vezetői, és (fél év után) még nem sikerült nukleáris háborút indítaniuk. Milyen nagyszerű! Micsoda eredmény!

A Donald-adminisztráció nagyszerű és legnagyobb sikere ellenére még mindig akad néhány dolog, amire szeret panaszkodni.

„A mexikói kormány sokkal okosabb, sokkal ravaszabb, és átküldik hozzánk a rosszakat, mert nem akarnak fizetni utánuk, nem akarnak gondoskodni róluk.”

Donald J. Trump, a republikánus elnökjelöltek első vitája, 2015. augusztus 6.

Gyakran hasonlítgatja a mexikóiakat más rossz emberekhez (például a németekhez, akik annyi drága autót exportálnak az Egyesült Államokba). A tetemes mennyiségű (többnyire 140 karakternél rövidebb) nyilatkozata miatt az „álhír” New York Telegraph (NYT) rengeteg energiát ölt Donald nyilatkozatainak tisztázásába és kommentelésébe. A nyilatkozatok ellenőrzéséhez van egy listájuk olyan tényekkel, amelyeket ők igaznak gondolnak. Donald nyilatkozatait három csoportba osztják: valós tények (az igaz tények listájának logikai következményei), túlzások (amelyek ugyan nem következnek az igaz tények listájából, de nem is mondanak ellent annak) és alternatív tények (amelyek ellentmondanak az újság ismereteinek).

Téged kértek fel arra, hogy írj egy programot, amely segít nekik Donald nyilatkozatainak a csoportosításában. Végtére is egy újságírónak nem könnyű végigmenni rajtuk és mindet ellenőrizni, nem igaz?

A bemenet specifikációja

A bemenet az alábbiakból tevődik össze:

• egy sor az n és m egész számokkal, ahol
  • n (1 ≤ n ≤ 200) a NYT által igaznak gondolt tények száma;
  • m (1 ≤ m ≤ 200) Donald nyilatkozatainak a száma;
• n sor, amelyek mindegyike egy, a NYT által igaznak gondolt tényt tartalmaz;
• m sor, amelyek mindegyike Donald egy nyilatkozatát tartalmazza.

Minden nyilatkozat az alábbi alakú: „a are worse than b”, ahol a és b sztringek, és azt állítja, hogy a (szigorúan) rosszabb, mint b. Az a és b sztringek sosem azonosak. Mindkét sztring hossza 1 és 30 karakter közé esik, és csak az angol ábécé kis- és nagybetűit tartalmazzák.

Megjegyezzük, hogy Donald nyilatkozatai olyan országokat is tartalmazhatnak, amelyről a NYT nem tud. Feltételezheted, hogy a „rosszabb” reláció tranzitív és hogy az igaz tények n soros listája nem tartalmaz ellentmondó állításokat. Érdekes módon Donaldot meggyőzte a sajtófőnöke (Morcos Sean), hogy ne találjon ki új országokat a tweetjeiben, így a bemeneten legfeljebb 193 különböző ország szerepel.

A kimenet specifikációja

Donald mind az m nyilatkozatára egyetlen sort kell a kimenetre írni, amely az alábbiak egyikét tartalmazza:

• „Fact” (tény), ha a NYT n ténye alapján az állítás igaz;
• „Alternative Fact” (alternatív tény), ha a NYT n ténye alapján az állítás ellenkezője igaz;
• „Pants on Fire” (a „Liar, liar, pants on fire” amerikai mondóka alapján), ha sem az állítás, sem az ellenkezője nem következik a NYT tényeiből.

Példa bemenet

1. 4 5
2. Mexicans are worse than Americans
3. Russians are worse than Mexicans
4. NorthKoreans are worse than Germans
5. Canadians are worse than Americans
6. Russians are worse than Americans
7. Germans are worse than NorthKoreans
8. NorthKoreans are worse than Mexicans
9. NorthKoreans are worse than French
10. Mexicans are worse than Canadians

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Fact
2. Alternative Fact
3. Pants on Fire
4. Pants on Fire
5. Pants on Fire

letöltés szöveges állományként

Eredeti feladat

ACM ICPC 2017 German Collegiate Programming Contest