Условие
Задача А. Стара Загора
---
Стара Загора е известен като града на липите, поетите, и правите улици. Под благоуханието на липите младежи рецитират стихотворения на възлюбените си. Ели също е от тях (възлюбените, не липите – тя няма как да е дърво, тъй като има цикъл). За разлика от другите девойки, обаче, тя е по-впечатлена от правите улици, отколкото от стихотворенията на момчетата.
"Колко ефективно може да стане всичко!" – мислеше си тя. Ако всяка улица се направи еднопосочна, трафикът би бил значително по-лек. Разбира се, за да се постигне добра инфраструктура, трябва пътят между важни двойки обекти да е възможно найудобен (например гарата и централният хотел; ветеринарният университет и зоопарка; стадионът и болницата; езиковата гимназия и пивоварната). Затова момичето планира да предложи на общината реструктуриране на улиците, така че всяка да стане еднопосочна, и в същото време за всяка двойка важни обекти (Ai, Bi) да е изпълнено, че може да се стигне от Ai до Bi ползвайки най-много един завой (максимум две улици – една вертикална и една хоризонтална).
За целите на задачата ще считаме града като правоъгълник с N хоризонтални улици (запад-изток или изток-запад) и M вертикални улици (север-юг или юг-север). Хоризонталните улици ще номерираме с числата от 1 до N, а вертикалните – с числата от 1 до M. В града има K (насочени) двойки обекти (Ai, Bi), за които трябва да е изпълнено, че може да се стигне от първия до втория ползвайки максимум две улици. Вашата задача е да установите дали улиците могат да бъдат насочени по такъв начин, че това условие да е изпълнено за всички K двойки обекти.
Вход
---
На първия ред на стандартния вход ще бъде зададено едно цяло число T – броя тестове, които вашата програма трябва да обработи. Всеки тест започва с три цели числа N, M и K – съответно броя хоризонтални и вертикални улици, и броя важни двойки обекти. Всеки от следващите K реда ще задава четири цели числа ARi, ACi, BRi, и BCi – съответно хоризонталната и вертикалната улица на обекта, от който се тръгва, следвани от хоризонталната и вертикалната улица на този, до който трябва да може да се стигне. Гарантирано е, че началната и крайната точка са различни.
Изход
---
За всеки тест на стандартния изход изведете по един ред, съдържащ "Yes", ако задачата може да бъде изпълнена за съответния тест, и "No" в противен случай.
Ограничения
1 ≤ T ≤ 10;
1 ≤ N, M ≤ 50;
1 ≤ K ≤ 200;
1 ≤ ARi, BRi ≤ N;
1 ≤ ACi, BCi ≤ M.
« Предходна страница
Решение
Въпрос