Toy Orange Making

Time limit6sMemory limit1024 MB

Summary

Treating each block as an edge between two colors, answer range queries: can blocks l to r all form circles, and if so, what is the minimum number of circles?

Level: Medium7 of 10
Topics: Graph, Union-find, Divide and conquer
Solved: No attempts yet

x

Jeonghu, a 17-year-old baby, is playing with his favorite snap-together toy. He wants to build an orange from it.

Jeonghu has $N$ snap-together toy blocks. Each block has two connectors, and two blocks can be joined by connecting their connectors. Each connector is painted one of $10^9$ colors, numbered from $1$ to $10^9$ . Block $i$ has a connector of color $a_i$ and a connector of color $b_i$ . The two connector colors are always different, so $a_i \neq b_i$ . The figure below shows three blocks.

An orange is round, so the blocks must form a circle to make one. Only connectors of the same color can be joined. The figure below shows a valid orange and two invalid ones. The first example is valid. The second cannot be joined because the connector colors differ. The third is not a valid orange because the blocks do not form a circle.

Jeonghu lined up the blocks and numbered them from 1 to $N$ . He wants to make oranges from a run of consecutive blocks, but he cannot work out how, so he asked you for help. Write a program that answers the following two kinds of queries.

Can you make at least one orange using all blocks in the range $[l_i, r_i]$ ? It does not have to be a single orange.
If so, what is the minimum number of oranges that can be made?

Examples2

Example 1
Input
```
4 3
1 2 3 2
2 3 1 1
1 3
1 4
2 4
```
Expected output
```
1
-1
1
```
Example 2
Input
```
4 2
1 2 3 4
2 1 4 3
1 2
1 4
```
Expected output
```
1
2
```