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
|
Для отправки решений необходимо выполнить вход.
|