繁杂的道路Ⅱ

Description:

      A城市长感谢你之前为A城交通做出的贡献。然而工程队在执行拆除任务时，愚蠢的拆除所有的道路。为了补救，市长再次找到了你。任务是这样的：市长把城镇分布图交给了你。上面标记了各个城镇的具体坐标，画明了哪些城镇之间可以建造双向道路。现在A城需要重建一些交通线，一条交通线是 v1->v2->v3->……->vk的通路（vi代表城镇）。允许交通线上只有一个城镇。由于施工需要，这条线路上城镇的x坐标值是递增的(x1<x2<…<xk)。现在需要你建造道路来构成交通网络并保证每一个城镇在且仅在一条交通线上。另外最重要的是交通线路数量要尽量少（市长依旧讨厌太复杂的东西）。

    例如，现在有5个城镇v1(1,1) , v2(2,2) , v3(3,3) , v4(4,4) , v5(5,5)。以下是可以建造的道路(v1,v2) , (v3,v1) , (v3,v4) , (v5 ,v4) 。 可以建造2条交通线 v1->v2 , v3->v4->v5 ； 或者建造3条交通线 v1-v2 , v3->v4 , v5。由于前者有更少的交通线，所以我们选择前者。但是不能建造v2->v1->v3->v4->v5的交通线，因为这不满足x坐标递增的原则。

Input:

第一行一个正整数n(1<=n<=200)，代表有多少个城镇。接下来n行，每行有两个整数xi，yi，代表城镇i的坐标。接着是一个整数m。代表可以建造的道路的数量。接下来是m行，每行两个整数p，q。代表可以建造道路(vp,vq)。(vp,vq)与(vq,vp)代表同一条可建道路。

Output:

一个整数，最少的交通线数量。

Sample Input:

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

Sample Output:

2

Note:

 

本题由旧版NOJ导入，来源：计算机学院/软件学院第二届ACM程序设计大赛