Movie Seating
Турнир за Купата на Декана, 2009
Time Limit: 0.1s, Memory Limit: 64MiB
Когато отиде на кино с компания, Ели винаги е обезсърчена от това колко хаотично сядат хората, напълно игнорирайки трудния за решаване проблем за разположение по начин, носещ максимална наслада. Това е нещо като задачата за търговския пътник, само където краищата са различни и не можете да поискате помощ от приятел, защото седи три седалки напред.


В случая ще дефинираме удовлетворението при дадено разположение като брой двойки доволни хора. Очевидно всеки човек има по един или двама в страни от себе си, с които може да си говори, но често хората пропускат приятелите отпред и отзад, които също са достижими. За това няма да броим тези вляво и вдясно, а ще казваме за двама човека че са доволни, ако са на два съседни реда и са един зад друг (тоест на една и съща колона) и, разбира се, са приятели.

Ели е отишла на кино с N-1 свои съученици, като всеки има билет за един от К-те реда, на кинозалата. Тъй като са компания, точното място на реда няма значение, тъй като всеки може да се размени с някой друг. Но поради хора, които не виждат, такива, които предпочитат да са по-назад и т.н. те не могат да сменят реда си.

Можете ли по даден брой хора, ред, на който стои всеки и граф на приятелствата, да определите колко най-много доволни двойки хора може да има?
Вход
На първия ред на стандартния вход ще бъдат зададени три цели числа N, M и K – съответно броят хора, броят приятелства, и броя редове в кинозалата. Вторият ред ще съдържа N цели числа R1, R2, ..., RN, отбелязващи, че i-тият човек стои на ред Ri. Следват М реда с двойки цели числа Аi Bi, отбелязващи, че Ai и Bi са приятели. Забележете, че редовете са достатъчно широки да поберат дори всичките N души.
Изход
На единствен ред на стандартния изход изведете едно цяло число – максималният брой доволни двойки.
Ограничения
  • 1 ≤ N ≤ 1,000
  • 0 ≤ M ≤ 10,000
  • 1 ≤ Ai != BiN
  • 1 ≤ RiK ≤ 20
Примерен Вход Примерен Изход
5 6 3 3 1 2 2 1 5 3 2 4 5 4 4 1 5 1 5 2 3
В примера има пет човека, които искат да отидат на кино. Първият е сам на реда си, така че може спокойно да седне зад своя приятел. Петият е приятел с всички останали, но може да стои само пред третия или четвъртия. Тъй като вторият ще остане доволен само ако стои пред четвъртия, то слагаме петия пред третия.
Мрън!