This page is still under construction.

Parts of this page are still being built. What you see may change.

Box Witch

Time limit3sMemory limit512 MB

Summary
A graph with N nodes and unit-capacity edges is modified by edge insertions and deletions, and after each change you must report the max flow from node 1 to node N.
Level

Medium7 of 10

Topics
Graph, Dynamic programming, Implementation, Brute force
Solved
No attempts yet

Problem

H.N.ELLY, the Box Witch, is an avid fan of a certain video site. Miki Sayaka wondered whether the Box Witch's strength changes with the transfer speed from that video site at any given time. So she wants to investigate the past transfer speeds (the amount of data transferred per unit time) from the video site to the computer owned by the Box Witch.

You are given the structure of the initial internet network and queries describing subsequent changes to the network structure. For each change, find the transfer speed from the video site to the computer owned by the Box Witch immediately after the change.

The internet is regarded as consisting of several transfer devices. The lines connecting them can send information in both directions, and the maximum transfer speed of each line is 1. The network always carries data so as to maximize the transfer speed of the data sent from the video site to the Box Witch.

Input

The input is given in the following format.

N E Q
F1 T1
F2 T2
…
FE TE
M1 A1 B1
M2 A2 B2
…
MQ AQ BQ

N is the number of transfer devices, including the video site and the computer owned by the Box Witch. The transfer device numbered 1 is the video site, and the transfer device numbered N is the computer owned by the Box Witch. E is the number of pairs of transfer devices connected in the initial state, and Q is the number of times the internet changes. The initial internet is represented by Fi and Ti being connected in both directions with transfer speed 1.

The changes to the network are given in chronological order. The j-th change represents that Aj and Bj have been connected if Mj is 1, and that the connection between Aj and Bj has been removed if Mj is 2.

Output

Output the transfer speed from the video site to the computer owned by the Box Witch immediately after each change.

Constraints

  • 2≤N≤500
  • 0≤E≤20,000
  • 1≤Q≤1,000
  • 1≤Fi≤N, 1≤Ti≤N, Fi≠Ti (1≤i≤E)
  • All pairs {Fi,Ti} are distinct.
  • 1≤Mj≤2, 1≤Aj≤N, 1≤Bj≤N, Aj≠Bj (1≤j≤Q)
  • At every stage of the network the following holds: any 2 transfer devices are connected by at most 1 line.
  • There is no query that connects 2 transfer devices that are already connected, nor any query that disconnects 2 transfer devices that are not connected by a line.

Examples4

  1. Example 1

    Input
    2 1 2
1 2
2 1 2
1 2 1
    Expected output
    0
1

  2. Example 2

    Input
    3 0 4
1 2 3
1 2 1
1 3 1
2 2 3
    Expected output
    0
1
2
1

  3. Example 3

    Input
    6 4 8
1 2
1 3
4 6
5 6
1 2 4
1 3 5
1 2 5
1 3 4
2 2 4
2 3 5
1 2 4
2 2 1
    Expected output
    1
2
2
2
2
2
2
1

  4. Example 4

    Input
    12 38 6
1 2
1 3
1 4
1 5
2 3
2 4
2 5
2 6
2 7
2 8
2 12
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
6 9
6 10
6 12
7 8
7 9
7 10
8 9
8 10
9 10
9 11
9 12
10 11
11 12
2 6 12
2 9 12
1 9 12
1 6 12
2 6 12
1 6 12
    Expected output
    3
2
3
4
3
4