[HackerEarth] View Russian Translation - P15100

P15100 [HackerEarth] View Russian Translation

提高

题目描述

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 ≤ 10^5
1 ≤ Ci ≤ 10^9
1 ≤ N, M, Q ≤ 10^3 in test data worth 20% of all points

SAMPLE INPUT
3 5
1 2 10
1 2 5
1 3 4
1 3 100
2 3 1000
10
+ 1
? 1
+ 2
? 1
- 1
? 1
? 3
+ 3
? 1
? 3

SAMPLE OUTPUT
0
0
5
5
4
0

输入格式

见题面

输出格式

见题面

样例输入

10 20
6 10 61130
9 10 10707
6 5 44869
1 4 51090
5 8 18187
1 5 84442
6 9 39334
2 4 32258
1 9 17533
4 10 44520
1 5 12675
6 3 30075
2 6 68108
3 5 12284
3 9 71460
1 5 80133
6 1 91418
3 5 48133
8 2 72074
9 7 76678
1000
? 8
? 10
? 4
? 1
+ 3
? 5
+ 1
+ 7
- 7
+ 5
- 1
- 3
? 10
? 4
+ 1
- 5
? 5
? 4
- 1
+ 6
? 2
- 6
+ 6
+ 2
? 2
+ 9
- 6
? 1
- 9
+ 7
- 2
? 10
- 7
+ 1
+ 10
- 1
- 10
? 3
? 7
+ 10
+ 9
+ 10
- 10
? 9
+ 5
- 10
- 9
+ 4
- 5
? 5
+ 7
? 9
? 1
+ 9
? 3
- 7
? 8
- 9
- 4
+ 3
+ 6
- 3
? 5
? 6
+ 1
- 6
? 3
- 1
? 6
+ 4
- 4
+ 2
+ 7
? 4
- 2
? 4
- 7
+ 7
? 1
+ 3
? 10
? 2
+ 8
- 7
- 3
? 5
+ 9
? 4
+ 1
- 1
+ 6
? 8
? 1
- 8
? 7
+ 2
? 6
? 5
- 2
- 9
? 10
- 6
? 3
+ 5
+ 3
? 4
- 5
- 3
? 4
? 4
? 4
? 9
+ 9
? 8
? 1
? 7
? 3
? 10
? 9
- 9
? 2
? 8
? 4
? 4
? 5
? 5
? 3
? 6
? 2
? 2
+ 10
+ 1
+ 10
? 7
- 10
+ 3
? 7
+ 3
- 1
? 2
? 3
- 10
+ 4
+ 1
- 1
- 3
+ 10
+ 5
+ 1
+ 4
- 4
+ 10
? 1
? 8
? 2
? 5
+ 5
+ 1
? 5
? 1
? 2
+ 5
- 5
- 1
- 5
? 9
? 1
? 10
+ 7
- 10
+ 10
+ 6
+ 5
+ 2
- 3
- 4
+ 4
+ 8
+ 5
+ 7
- 5
+ 3
? 1
+ 7
+ 6
? 3
? 10
+ 3
? 7
- 5
+ 6
? 1
+ 2
? 6
- 6
- 2
? 10
+ 8
+ 6
+ 8
+ 9
+ 4
- 6
- 3
+ 9
+ 2
? 10
- 10
- 4
- 6
- 5
? 3
? 6
- 9
? 9
- 10
? 1
- 2
- 8
? 3
+ 10
- 7
? 7
- 10
+ 2
+ 2
- 2
? 6
- 1
? 10
- 8
- 8
+ 2
? 6
- 7
+ 2
+ 4
? 2
- 9
- 7
? 9
+ 4
? 2
? 4
+ 3
? 8
- 4
- 6
+ 8
- 2
+ 9
+ 3
? 5
+ 6
+ 8
? 7
+ 7
? 10
- 8
? 9
? 9
- 3
? 1
+ 9
? 3
- 8
? 2
+ 5
? 7
- 6
+ 6
+ 2
? 10
? 8
- 2
+ 3
- 2
- 9
+ 4
? 3
? 10
+ 8
? 4
+ 9
- 3
+ 1
- 4
+ 7
? 5
? 7
? 1
+ 10
- 3
- 5
+ 7
- 10
- 7
? 10
- 9
+ 7
? 10
- 7
? 1
? 8
+ 4
- 7
- 7
+ 4
? 6
+ 9
+ 4
? 3
+ 6
- 9
+ 7
? 3
- 1
- 4
+ 2
? 10
- 4
? 2
- 2
? 6
- 2
- 4
- 3
+ 6
? 6
- 6
- 8
+ 10
? 10
- 4
- 7
? 6
? 10
+ 7
+ 6
+ 4
? 4
+ 3
? 9
- 6
? 2
+ 6
- 6
- 2
- 9
- 10
- 4
+ 6
- 4
+ 10
? 8
+ 5
+ 7
+ 4
? 3
- 7
- 5
- 10
- 6
? 8
+ 1
? 9
- 6
- 7
? 4
- 1
? 7
+ 2
+ 8
? 6
? 8
- 4
+ 2
+ 8
? 5
? 5
+ 8
+ 10
+ 10
- 8
? 6
+ 1
- 10
? 8
+ 7
+ 1
- 2
+ 9
- 2
+ 3
+ 5
- 6
- 8
? 5
+ 3
? 4
? 7
? 9
? 6
- 1
? 8
+ 8
- 7
+ 6
+ 5
+ 6
+ 8
+ 8
+ 9
- 10
? 7
- 3
? 9
- 8
? 9
- 5
+ 3
? 3
- 9
+ 7
? 3
? 8
+ 6
? 8
? 10
? 9
- 1
? 2
+ 4
+ 2
? 7
- 3
+ 1
+ 3
? 8
+ 7
- 3
- 6
- 8
+ 6
- 3
+ 6
- 2
+ 5
? 8
? 7
? 1
+ 6
? 5
- 6
+ 2
+ 1
- 3
- 2
? 10
- 9
? 1
- 7
? 4
- 8
? 2
? 10
? 4
- 5
? 10
? 10
? 7
+ 3
- 1
- 6
- 4
+ 1
- 6
- 1
? 2
+ 2
- 3
+ 3
? 3
- 8
+ 5
+ 7
- 2
- 6
+ 7
? 8
- 6
- 7
? 9
+ 3
+ 3
- 3
? 4
+ 2
- 3
? 2
? 4
? 3
+ 10
- 5
- 7
? 8
? 9
+ 8
- 8
? 1
- 5
+ 7
- 2
+ 8
? 10
- 10
- 7
? 10
? 4
- 1
? 7
+ 1
- 8
+ 9
? 8
+ 6
- 3
- 1
? 9
? 3
? 7
? 4
+ 9
? 7
? 9
+ 7
- 9
? 8
+ 3
+ 2
? 4
+ 9
? 3
+ 6
? 8
- 6
+ 10
+ 4
+ 6
? 6
- 7
+ 5
+ 3
? 6
- 10
+ 3
? 2
- 9
? 3
- 5
? 8
+ 3
- 2
? 2
+ 8
? 7
+ 4
+ 9
+ 5
? 3
? 9
+ 10
- 9
- 9
- 10
? 8
+ 6
? 2
+ 5
+ 10
- 3
? 2
- 3
? 8
+ 9
+ 6
- 6
+ 5
- 6
+ 5
+ 4
- 7
? 7
? 3
- 10
? 8
? 1
- 6
+ 3
? 10
+ 7
+ 8
- 8
- 7
- 6
? 2
- 3
? 5
+ 7
+ 6
? 6
+ 6
+ 10
- 10
+ 3
? 5
- 5
+ 3
- 5
+ 3
- 3
+ 5
? 5
- 4
- 5
? 7
- 9
- 3
? 9
- 5
- 8
- 4
- 5
? 4
+ 3
+ 9
- 6
+ 7
- 3
+ 3
- 6
+ 2
? 6
? 3
- 4
? 10
+ 8
? 2
+ 9
? 5
- 7
+ 9
- 3
- 2
- 3
? 4
? 3
- 8
? 10
- 3
+ 8
+ 4
- 4
- 9
? 10
+ 4
+ 9
- 9
? 1
- 3
- 4
+ 9
- 9
+ 1
- 9
+ 10
+ 1
? 9
? 9
- 1
? 2
+ 9
? 10
+ 5
- 5
+ 9
- 9
? 3
? 5
- 10
? 2
? 8
? 3
- 9
+ 2
? 2
? 1
- 9
+ 2
- 2
- 1
- 2
+ 7
? 9
- 7
- 8
- 7
? 5
+ 3
- 3
? 2
? 7
? 1
? 3
+ 8
? 7
? 8
? 10
? 1
+ 5
- 5
+ 7
? 9
+ 9
+ 9
- 8
- 9
+ 10
+ 1
+ 2
- 1
+ 4
+ 1
- 10
+ 7
? 3
- 7
+ 9
? 3
+ 1
- 2
? 10
? 6
+ 5
- 1
? 1
- 7
+ 3
+ 3
? 4
? 7
- 9
+ 2
+ 7
+ 1
- 1
+ 2
- 9
+ 8
- 5
+ 6
+ 5
? 6
+ 1
+ 1
- 4
+ 1
? 7
+ 4
+ 1
? 1
? 9
? 1
+ 3
? 1
- 1
+ 6
- 3
? 7
? 1
+ 4
+ 8
- 8
? 8
+ 6
? 6
? 1
- 4
+ 7
? 10
? 6
- 2
+ 6
- 6
? 6
- 6
? 6
? 2
- 6
? 5
+ 4
+ 1
? 2
+ 4
- 1
? 4
+ 4
+ 6
- 3
? 3
+ 2
+ 7
- 5
- 6
+ 9
- 4
- 7
? 2
? 4
- 4
? 8
+ 6
? 10
- 1
- 7
? 1
? 10
- 4
? 1
- 7
+ 8
- 1
? 6
+ 6
+ 7
? 9
+ 10
- 8
- 2
- 7
? 3
? 3
- 3
+ 10
+ 7
+ 5
? 9
+ 5
- 10
- 6
- 8
+ 4
? 3
+ 6
+ 9
? 6
- 4
? 3
- 4
- 6
? 3
? 9
- 10
? 5
? 3
+ 7
- 5
- 1
+ 1
+ 6
- 1
+ 2
- 2
+ 6
+ 8
- 7
? 3
? 5
+ 3
? 4
? 8
- 6
- 6
+ 9
+ 2
+ 8
+ 10
? 3
? 5
? 8
? 10
- 9
+ 10
+ 3
? 7
? 2
- 7
+ 10
- 3
? 2
? 6
+ 8
? 8
? 3
+ 2
- 2
? 7
? 9
? 9
? 7
? 7
- 8
+ 1
+ 6
? 6
+ 8
? 9
+ 4
+ 2
- 8
? 7
- 4
+ 1
+ 4
+ 3
- 5
? 2
? 1
? 6
+ 5
- 3
- 1
- 9
+ 2
? 8
? 9
? 10
+ 6
? 1
+ 6
? 9
? 10
- 10
- 8
+ 1
- 1
? 4
- 4
- 9
+ 6
+ 7
+ 5
+ 3
? 5
+ 10
- 6
? 2
? 9
+ 9
+ 6
- 1
+ 8
- 10
- 2
? 5
? 5
- 6
- 3
? 6
? 1
? 5
+ 3
+ 7
+ 10
- 7
+ 3
+ 4
+ 1
+ 6
+ 9
+ 10
- 10
- 1
+ 8
? 7
- 2
+ 1
? 1
+ 7
? 3
- 9
+ 9
? 10
+ 8
- 8
+ 3
- 6
- 6
+ 3
- 5

样例输出

题目信息

时间限制	2000 ms
内存限制	256 MB
难度	提高
提交数	0
通过数	0
通过率	0.0%

登录后 AI 解题查看题解登录后提交