Colorful_graph (OOI qualification)
Time limit: 1.5 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: offline queries, bitmask, connectivity, union-find

# Colorful graph

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1.5 seconds     |
| Memory limit: | 256 megabytes   |

Given an undirected graph on $n$ vertices with $m$ edges numbered from 1 to $m$. Each edge is colored in one of $k$ colors. The $i$-th edge connects the vertices $v_i$ and $u_i$ and has the color $c_i$.

Let's call a graph good if it is possible to leave exactly $n - 1$ edges in it so that the graph is connected and there is at least one edge of each color among the edges left.

Given $q$ changes in the colors of the edges of the graph. Each change is described by two numbers $e_i$ and $w_i$ and means that the color of the $e_i$-th edge becomes equal to $w_i$. After each change, determine if it is good.

### Input

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 100\,000$, $1 \le m \le 100\,000$, $1 \le k \le 8$) — the number of vertices, edges and colors respectively.

The following $m$ lines contain a description of the edges. $i$-th of them contains three numbers $v_i$, $u_i$ and $c_i$ ($1 \le v_i, u_i \le n$, $1 \le c_i \le k$, $v_i \ne u_i$) — the endpoints of the $i$-th edge and its color, respectively.

The next line contains a single integer $q$ ($1 \le q \le 100\,000$) — the number of changes.

The following $q$ lines contain a description of the changes. $i$-th of them contains two integers $e_i$ and $w_i$ ($1 \le e_i \le m$, $1 \le w_i \le k$) — edge number and its new color.

It is guaranteed that there are no loops and multiple edges in the graph.

#### Output

In the $i$-th line, print «Yes» (without quotes) if the graph after the $i$-th query is good, and «No» (without quotes) otherwise.

## Examples

| standard input | standard output |
|----------------|-----------------|
| 5 5 3          | No              |
| 3 4 1          | Yes             |
| 1 5 2          | Yes             |
| 3 2 3          | No              |
| 1 4 3          | Yes             |
| 3 5 3          |                 |
| 5              |                 |
| 1 3            |                 |
| 4 1            |                 |
| 5 1            |                 |
| 2 1            |                 |
| 3 2            |                 |
| 2 1 1          | Yes             |
| 1 2 1          |                 |
| 1              |                 |
| 1 1            |                 |

#### Note

In the first example, after the first change, the graph looks like this:

![](_page_1_Figure_0.jpeg)

In this case, there are no edges of the color 1, so the condition of the problem cannot be met. After the second change, the graph looks like this:

![](_page_1_Figure_2.jpeg)

The edges that can be left are highlighted in red. This example is correct, since among these edges there are all the colors 1, 2 and 3, and they also form a connected graph.

## Scoring

The tests for this problem consist of 8 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Score | Additional constraints $k$ | Required groups | Comment          |
|-------|-------|--------------------------|-----------------|------------------|
| 0     | 0     | -                        | -               | Samples.         |
| 1     | 10    | $k \le 1$                 | -               |                  |
| 2     | 9     | $k \le 2$                 | 1               |                  |
| 3     | 15    | $k \le 3$                 | 0 - 2           |                  |
| 4     | 16    | $k \le 4$                 | 0 - 3           |                  |
| 5     | 14    | $k \le 5$                 | 0 - 4           |                  |
| 6     | 13    | $k \le 6$                 | 0 - 5           |                  |
| 7     | 12    | $k \le 7$                 | 0 - 6           |                  |
| 8     | 11    | $k \le 8$                 | 0 - 7           | Offline-testing. |

Starter code:

Grader code:

Setup script:

Evaluation script: