- Time limit: 1.00 s
- Memory limit: 512 MB
Syrjälä's network has computers and connections between them. The network consists of components of computers that can send messages to each other.
Nobody in Syrjälä understands how the network works. For this reason, if a connection breaks down, nobody will repair it. In this situation a component may be divided into two components.
Your task is to calculate the number of components after each connection breakdown.
Input
The first input line has three integers , and : the number of computers, connections and breakdowns. The computers are numbered .
Then, there are lines describing the connections. Each line has two integers and : there is a connection between computers and . Each connection is between two different computers, and there is at most one connection between two computers.
Finally, there are lines describing the breakdowns. Each line has two integers and : the connection between computers and breaks down.
Output
After each breakdown, print the number of components.
Constraints
Example
Input:
5 5 3 1 2 1 3 2 3 3 4 4 5 3 4 2 3 4 5
Output:
2 2 3