Locking Doors
Description
You just started a new job at a shopping mall, and as it goes, you got the shittiest task of all: closing down at night. The mall consists of many rooms (which can be shops, hallways, or other public spaces) with open doors between them that must be closed. You can walk through a door both ways if it is open, but annoyingly, each door can only be locked from one of the two rooms it connects.
Your supervisor already locked the main entrance of the shopping mall, and left you inside with the task to lock all the doors. In order to do so, you may request additional exits to be installed in some of the rooms. If a room has an exit, then you are able to enter or leave the shopping mall through that room.
What is the minimal number of exits you need to request in order for it to be possible to lock all the doors and then leave the building?
The input consists of:
- One line with two integers $n$ and $m$ ($2\leq n \leq 10^5$, $1\leq m \leq 10^6$), the number of rooms and doors, respectively.
- Then follow $m$ lines, each containing two distinct integers $a$ and $b$ ($1 \leq a,b \leq n$, $a \neq b$), indicating a door connecting rooms $a$ and $b$ which can only be locked from room $a$.
Output the minimal number of exits that need to be installed.
Input
The input consists of:
- One line with two integers $n$ and $m$ ($2\leq n \leq 10^5$, $1\leq m \leq 10^6$), the number of rooms and doors, respectively.
- Then follow $m$ lines, each containing two distinct integers $a$ and $b$ ($1 \leq a,b \leq n$, $a \neq b$), indicating a door connecting rooms $a$ and $b$ which can only be locked from room $a$.
Output
Output the minimal number of exits that need to be installed.
2 1
1 2
3 2
2 1
3 1
5 4
1 2
3 1
4 1
5 1
10 14
1 2
2 1
3 4
3 5
4 6
5 6
6 3
7 8
8 9
9 7
1 8
2 10
4 9
5 10
1
2
3
2