Code Submission Evaluation System Login

Datatähti Open 2018

 Start: N/A End: N/A

CSES - Datatähti Open 2018 - NetworkCSES - Network

Network

 Time limit: 1.00 s Memory limit: 512 MB

Syrjälä's network consists of $n$ computers and $n$ connections between them. At the moment it is possible to send a message between any two computers.

Your task is to calculate the number of essential connections: if such a connection is removed from the network, it is not possible to send a message between some two computers.

Input

The first input line contains an integer $n$: the number of computers. The computers are numbered $1,2,\ldots,n$.

After this, there are $n$ lines that describe the connections. Each line has two integers $a$ and $b$: there is a connection between computers $a$ and $b$.

There is at most one connection between two computers, and there are no connections from a computer to itself.

Output

Print one integer: the number of essential connections.

Example

Input:
7 1 2 2 3 2 4 4 5 2 5 5 6 6 7

Output:
4

Explanation: The essential connections are $(1,2)$, $(2,3)$, $(5,6)$ and $(6,7)$.

Subtask 1 (28 points)
• $2 \le n \le 100$
Subtask 2 (72 points)
• $2 \le n \le 10^5$