HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50700 - Candidates for the Mayor

Section problems

• 50255 - Bishops
• 50261 - Roads
• 50690 - Parliament
• 50700 - Candidates for the Mayor
• 50692 - How much money?
• 50694 - The Cheapest Flight
• 50841 - My grand-grand-grandfather
• 50697 - Base Stations
• 50695 - Longest link between neurons
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Sidrit Reka.

Candidates for the Mayor

The prime minister of Albania is not very sure for the candidates of his party for the city of Tirana. He knows that there are a lot of candidates for this important job so he asks your help to find him the best candidates. The prime minister wants the candidates to have connections or relations with a lot of people. But these relations are a bit special. If person A knows person B and person B knows person C, there exists a relation between A & B, B & C, and A & C, but the last relation is not as strong as the previous two since it is not a direct one.

The prime minister will give you a distance as a parameter that defines the maximum length that a candidate can reach other persons through relations and another number which defines the number of persons that each candidate should be related to. You should give him the sorted list of candidates that fulfill the given conditions.

Input specification
In the first line you will be given four integers, v, e, n, d where 3 <= v <= 1000, 0 <= e <= 3000, 2 <= n <= 100, 5 <= d <= 100. v determines the number of people that can be chosen as candidates, e determines the number of relations that exist, n determines the number of persons that each candidate should be related to and d determines the maximum length that a candidate can reach other persons through relations. In the following e lines, you will be given 3 integers, a, b and c, where 0 <= a, b <= v-1 and 1 <= c <= 20. Each of these lines determines a relation between two people a,b and c is the length of the relation. (smaller length, stronger relation)

Output specification
Print the sorted list of people that can be chosen as candidates by fulfilling the given conditions. If there is no people that fulfill the given conditions, output "There are no possible candidates!".

Sample Input I
4 3 2 5
0 2 4
0 3 5
3 1 6
Sample Input II
4 5 2 5
0 2 4
0 3 6
3 1 6
3 1 2
2 1 1
Sample Output I
0
Sample Output II
0 1 2 3


Для отправки решений необходимо выполнить вход.

www.contester.ru