You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

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\%$的数据，$n\le 5,k\le 5,p\le 5$。

对于$60\%$的数据，$n\le 100,k\le 100,p\le 100$。

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