### PROBLEM LINK:

**Author:** Full name

**Tester:** Full name

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Disjoint Set Union

### PROBLEM:

You’re given N gears. Gear i has A_i teeth. You have to process M queries of the types:

- Change A_X to C;
- Connect gears X and Y;
- Find speed of gear Y if X rotates with speed V;

## Note

If gears i and j are connected and i rotates with speed V then j rotates with speed -V \cdot \tfrac{A_i}{A_j}. Also it is possible that gears are blocked, in this case you should output 0.

### QUICK EXPLANATION:

First, maintain bipartite checks in online with dsu. Then to answer third query use formula:

Here c_X and c_Y are colors of vertices X and Y (either 0 or 1). If they don’t lie in same component or their component is blocked, output 0.

### EXPLANATION:

Consider gears i and j in the same component. Let i=v_1,\dots,v_k=j be arbitrary path from i to j. Then:

Which is direct formula to answer third query. You only have to know parity of k-1 to answer it. When can this parity depend on path we choose? If and only if there are pathes of different parity, which means that there is a cycle of odd length in the graph. Indeed, we can see that gears connected component will be blocked if and only if it’s not bipartite. Thus to solve a problem we have to maintain bipartite checks in online with queries of adding new edges. This can be done in straight-forward manner with disjoint set union through merging sets.

Let’s assign for each vertex some random color. Now when we add new edge if it connects different connected components, we will go through smallest of them if necessary (if kept colors are same for endpoints) and reverse color of each vertex in it. Otherwise we just check that the edge connects vertices of different colors and if no, we will say that this component is blocked from now on. This will give us solution with final complexity of O(n\log n) time and memory usage.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.