Benny and Friends
Practice
4.1 (35 votes)
Data structures
Minimum spanning tree
Approved
Hard
Disjoint set
Problem
35% Success 134 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

View Russian Translation

Benny is living in a big country. This country has N cities and M biderectional roads between cities. Each road is characterized by three integers - u, v and c where u and v are the cities connected by this road and c is the length of this road. There can be more than one road between two cities. There no roads connecting city to itself.

Benny has many friends. They really like to travel therefore they are not staying at home all the time. Sometimes they return to their homes or conversely leave their homes. You will be given all information about Benny's friends.

Every time when Benny gets bored she wants to visit some of her friends. She wants to find such friend that path between Benny's current city and friend's city has the minimal inconvenience.

Inconvenience of the path which consists of K edges with lengths C1, C2, ..., Ck equals to maximum number among C1, C2, ..., Ck.

You are given a graph with N cities and M biderectional roads. You have to process Q queries. Each query has on of the following types:

  • + v -- means that one of Benny's friends return from the journey and is staying at city with index v.
  • - v -- means that one of Benny's friends leaves his home which is located in the city with index v.
  • ? v -- means that Benny wants to visit one of her friend that the path between them has the minimal inconvenience. This friend must be at home in this moment. Benny's current location is the city with index v.

For each query of type "?" output in a single line one integer - minimal inconvenience of the path to her friend or -1 if she can not reach home of any friend.

Input format

The first line contains two integers N and M denoting the number of cities and number of roads. Each of the next M lines contain three integers u, v, c, denoting the road between cities u and v with length c. The next line contains a single integer Q denoting the number of queries. The following Q lines contain descriptions of queries. Each query consists of one character denoting the type of query, space, and the index of vertex.

Output format

For each query of type "?" output in a single line one integer - minimal inconvenience of the path to her friend or -1 if she can not reach home of any friend.

Constraints

  • 1 ≤ N, M, Q ≤ 105
  • 1 ≤ Ci ≤ 109
  • 1 ≤ N, M, Q ≤ 103 in test data worth 20% of all points

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
4 votes
Tags:
AlgorithmsHardSquare Root Decomposition
Points:30
150 votes
Tags:
ReadyBrute-force searchEasy-MediumApprovedBreadth-first search
Points:30
12 votes
Tags:
RecursionDynamic ProgrammingEasy-MediumBacktracking