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


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

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

Можете ли по даден брой хора, ред, на който стои всеки и граф на приятелствата, да определите колко най-много доволни двойки хора може да има? На първия ред на стандартния вход ще бъдат зададени три цели числа N, M и K – съответно броят хора, броят приятелства, и броя редове в кинозалата. Вторият ред ще съдържа N цели числа R₁, R₂, ..., R_N, отбелязващи, че i-тият човек стои на ред R_i. Следват М реда с двойки цели числа А_i B_i, отбелязващи, че A_i и B_i са приятели. Забележете, че редовете са достатъчно широки да поберат дори всичките N души. На единствен ред на стандартния изход изведете едно цяло число – максималният брой доволни двойки.

• 1 ≤ N ≤ 1,000
• 0 ≤ M ≤ 10,000
• 1 ≤ A_i != B_i ≤ N
• 1 ≤ R_i ≤ K ≤ 20

Примерен Вход	Примерен Изход
5 6 3 3 1 2 2 1 5 3 2 4 5 4 4 1 5 1 5 2	3