Magic Roads#6451
You have entered a magical land. As it turns out, its structure is no different from that of an ordinary one: it consists of several cities, some of which are connected by bidirectional roads. Each road has a certain length, and — by an astonishing magical coincidence — all these lengths are distinct.
However, unlike a typical kingdom, in the magical land, the king can do whatever he desires. He can order the construction of a road, or the destruction of an existing one. But such commands quickly became boring for him...
Recently, the king came up with a new amusement. He issued a decree stating that all roads originating from a given city should change their state to the opposite. Each road can be in one of two states: either active (in use) or inactive.
One day, you were summoned before the king. He was in a cheerful mood and decided to play a little game with you. At first, he wanted to ask:
What is the length of the shortest road among all the roads in the magical land?
But then he thought that would be too easy and came up with a new, more challenging question:
Find the -th shortest road among the currently active roads (if one exists).
As the king of the magical land—where the sun always shines over rainbow-colored fields—was known for being rather particular about rules, he expects precise answers to all his questions. Therefore, you must answer all questions accurately so the game may continue.
The first line contains three integers n, m, q (2 \le n \le 500,\, 1 \le m \le n \cdot (n - 1) / 2,\, 1 \le q \le 200000) — the number of cities, the number of roads, and the number of royal queries, respectively.
The next lines describe the roads. Each line contains three integers: a_i, b_i, c_i (1 \le a_i, b_i \le n,\, 1 \le c_i \le 10^9) — the indices of the cities connected by a road, and the length of the road.
It is guaranteed that:
there is at most one road between any pair of cities,
no road connects a city to itself,
all road lengths are distinct.
Initially, all roads are active.
The next lines describe the king's queries.
Each line starts with an integer x_i:
If x_i = 1, then it is followed by a number v_i (1 \le v_i \le n) — the city from which all outgoing roads should toggle their state.
If x_i = 2, then it is followed by a number k_i (1 \le k_i \le m) — the king asks for the number of the k_i-th shortest active road.
For each query of the second type (x_i = 2), output a single integer on a separate line:
the number of the k_i-th shortest currently active road;
or if there are fewer than k_i such roads.
The roads are numbered in the same order as given in the input.
مثال 1
مثال 2