Cisco OA 2022 - Mail Rooms for Office Buildings

Company ABC has a corporate campus with multiple buildings. These buildings may or may not be connected to one another.

Goal
Please help Alisa determine the least number of mail rooms to be set up so that all buildings are serviced with the following considerations.

Constraints

• A building can host only 1 mail room.
• A building having a mail room will also service buildings directly connected to it. Hence, those directly connected buildings may not host a mail room unless required otherwise.
• A building may or may not be connected to other buildings. In such a case, it would need its own mail room.
• The number of each building X is a random integer where 0 <= X <= 10^4.
• The total number of buildings is P where 0 <= P <= 10^4.
• The number of connections is N such that 0 <= N <= 1000.

Inputs

• The first line contains an integer P, i.e. the total number of buildings in the campus.
• The second line contains an integer N, i.e. the number of connections. Each connection is represented as 'X Y', e.g., '10 20', which indicates a link between Building 10 and Building 20.
• Next N lines contain the first building connected by the link, i.e. X. The other endpoint would be at the index of the current line + N. The next N lines contain the second building connected by the link, i.e. Y.

Output
Number indicating the minimum number of mail rooms needed.

Example 1:

Input:

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

Output: 2