CSES - Network Breakdown
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Syrjälä's network has nn computers and mm 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 nn, mm and kk: the number of computers, connections and breakdowns. The computers are numbered 1,2,,n1,2,\dots,n.

Then, there are mm lines describing the connections. Each line has two integers aa and bb: there is a connection between computers aa and bb. Each connection is between two different computers, and there is at most one connection between two computers.

Finally, there are kk lines describing the breakdowns. Each line has two integers aa and bb: the connection between computers aa and bb breaks down.

Output

After each breakdown, print the number of components.

Constraints

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1km1 \le k \le m
  • 1a,bn1 \le a,b \le n

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