#C2023E. 银河系峰会
银河系峰会
题目描述
在进入银河系大航海时代后,我们发现了许多地外文明,并且建立起了银河系联邦。不久之后,银河系联邦的第一次峰会即将举行,每个文明都会派一名代表参加峰会。但是由于银河系有太多不同的文明,语言的不同导致代表们的交流成为了困难。
在这次峰会上,有个文明代表参加。我们知道每位代表所掌握的语言(一位代表可能甚至不会本文明的语言这也很合理)。如果两个代表掌握了同一门语言,那么他们就能够直接交流;如果两个代表通过若干个代表的“翻译”能够传达彼此的意思,那么他们就能够间接交流。
例如,假设代表a会语言1,代表b会语言1和2,代表c会语言2,那么a和c就可以通过b做到间接交流。
现在,作为银河系联邦主席,为了银河系联邦的长治久安,你需要让每位代表两两之间都可以进行直接或间接的交流。你发明了一种学习机,可以让一位代表学会一种他不会的语言。但是学习机的使用会消耗大量的能量,因此你想知道最少使用多少次学习机才能达成你的目标。
输入格式
输入第一行包含个整数,表示参会代表人数,语言数和已知的信息数。 接下来行,每行两个整数,代表第个文明的代表会第种语言。
输出格式
输出仅包含一行一个整数,表示最少需要使用学习机的次数。
样例
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
范围
对于的数据,。
对于的数据,。
对于的数据,$1\le u\le n\le 100000,1\le v\le k\le 100000,0\le p\le 100000$。
相关
在下列比赛中: