Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Osman Ay.
Base Stations
Question:
A GSM Company has recently built new base
stations to extend his coverage area. The fiber optic
communication cables are used to connect any two base
stations. The company hired you to be sure that all
the base stations are connected each other directly or
via some other base stations. The company has the list
of the directly connected base stations. You should make
a program that prints number of the additional connections
needed to fulfill the company's demand.
Input specification
The first line of the input contains two integers N
(1 ≤ N ≤ 1000) and M (1 ≤ M ≤ 100000).
N is the number of the base stations and M is
the number of the connections. The base stations are
numbered from 1 to N. Each of the following M lines
represents a unique connection with a pair of integer:
x and y (1 ≤ x, y ≤ N) where, x and y denotes the
station numbers. The stations are numbered from 1 to N.
Output specification
The output contains a single integer that is number
of the additional connections. If all the base
stations are already connected each other,
print 0.
Sample Input
7 8
1 5
1 4
3 7
2 4
2 6
2 5
5 6
1 6
|
Sample Output
1
|
Для отправки решений необходимо выполнить вход.
|