U239755 星门重建

根据《拉格朗日简史》记载，远古之时，太阳系的边界就是航行技术的极限，奥尔特星云似乎就是人类文明对外探索的桎梏，真正的太空是如此遥不可及。然而，开拓的野心和对极限的追求从未停止，一次偶然的实验，在星球的引力平衡点(拉格朗日点)上，空间共振现象被发现了，我们在此修建了空间共振装置，在数百个甲子(1甲子为60地球年)，上代人的共同建设下，星门诞生了...... 穿过星门，彼端是无数未知的星系。历经坎坷，空间共振点的使用方法被掌握，一个划时代的名字诞生了:拉格朗日节点。星系航行的新篇章，就此开启，宏伟，丰富，辽阔，富足。拉格朗日网络带来了前所未有的繁荣。在此占据银河系三分之二的神圣群星帝国雄起，成为了人类文明历史上最繁荣，最宏伟的一章。人类文明，也成为了银河系中最神圣的文明 与此同时，不满、矛盾、冲突和战火也在网络中滋长，随着时钟座136星系护卫舰队旗舰“特拉法加”号的殉爆，无敌舰队不败的神话被打破，由海雷丁家族带领的反叛军摧毁了一座由又一座旧帝国的前哨岗，一支又一支的神圣群星帝国的舰队被歼灭，旧帝国分崩离析，新的实力在残骸中诞生，不断向我们展示着太空的另一面。 终于，随着巨型空间站安东塔斯城的建立，拉格朗日网络被重新点亮，开拓的旅程再度起航。人们对拉格朗日系统进行了修复，对在战火中成为废墟的星门残骸进行了重建。

现在有n个星系，编号为1~n，受到共振点曲率高度的影响，只有某k组星系可以连接，而且如果两星系之间只有一方有星门的话，则迁跃只能是单向的（有星门的一方迁跃到另一方），两方都有则是双向的。战火之后，保留了一部分星门，共m个，此外可以再次进行其他星系星门的重建。由于战火无处不在，为了防止拉格朗日网络被切断，需要每个星系至少需要两个能**直接**迁跃到此星系的星门，而且要使所有星系联通，现在需要求出至少要再建设多少星门才能满足条件。

第一行三个整数，n,m,k,接下来m行，每行一个整数，表示保留着星门的星系编号，接下开k行，每行两个整数x,y,表示x星系和y星系之间可以连接。

输出符合还需建设星门的数量，无解输出-1。

1