交头接耳 / talking

题目描述

在一间教室中总有很多同学会交头接耳。为了保证课堂质量，老师决定在课桌之间设置q个纵横过道使得过道两边的同学无法交头接耳。教室可视作一个n*m的网格，每个网格上都是一个同学。现给出k对会交头接耳的同学（保证每一对都左右相邻或者前后相邻），请问通过设置过道最少能使交头接耳的同学对数减少为多少？

输入格式

第一行4个整数n，m，k，q，意义如题目所描述。

接下来行每行4个整数，x1，y1，x2，y2，表示坐标为（x1,y1）与（x2,y2）的同学会交头接耳。

输出格式

输出共一行，如题目所描述。

输入输出样例

样例1 输入

4 5 5 2
1 1 1 2
1 5 2 5
3 2 3 3
4 3 3 3
3 5 4 5

样例1 输出

2

测试点数据范围

#1 - #3 1 ≤ n,m ≤ 2000,1 ≤ k,q ≤ 2000,1 ≤ x ≤ n , 1≤ y ≤ m

#4 - #6 1 ≤ n,m ≤ 200000,1 ≤ k,q ≤ 200000,1 ≤ x ≤ n , 1≤ y ≤ m

#7 - #10 1 ≤ n,m ≤ 200000000,1 ≤ k,q ≤ 200000,1 ≤ x ≤ n , 1≤ y ≤ m