#C2023E. 银河系峰会

银河系峰会

题目描述

在进入银河系大航海时代后,我们发现了许多地外文明,并且建立起了银河系联邦。不久之后,银河系联邦的第一次峰会即将举行,每个文明都会派一名代表参加峰会。但是由于银河系有太多不同的文明,语言的不同导致代表们的交流成为了困难。

在这次峰会上,有nn个文明代表参加。我们知道每位代表所掌握的语言(一位代表可能甚至不会本文明的语言这也很合理)。如果两个代表掌握了同一门语言,那么他们就能够直接交流;如果两个代表通过若干个代表的“翻译”能够传达彼此的意思,那么他们就能够间接交流。

例如,假设代表a会语言1,代表b会语言1和2,代表c会语言2,那么a和c就可以通过b做到间接交流。

现在,作为银河系联邦主席,为了银河系联邦的长治久安,你需要让每位代表两两之间都可以进行直接或间接的交流。你发明了一种学习机,可以让一位代表学会一种他不会的语言。但是学习机的使用会消耗大量的能量,因此你想知道最少使用多少次学习机才能达成你的目标。

输入格式

输入第一行包含33个整数n,k,pn,k,p,表示参会代表人数,语言数和已知的信息数。 接下来pp行,每行两个整数u,vu,v,代表第uu个文明的代表会第vv种语言。

输出格式

输出仅包含一行一个整数,表示最少需要使用学习机的次数。

样例

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

范围

对于30%30\%的数据,n5,k5,p5n\le 5,k\le 5,p\le 5

对于60%60\%的数据,n100,k100,p100n\le 100,k\le 100,p\le 100

对于100%100\%的数据,$1\le u\le n\le 100000,1\le v\le k\le 100000,0\le p\le 100000$。