Birmingham

Είναι γνωστό ότι όλες οι ιπποδρομίες στο Μπέρμιγχαμ είναι καθορισμένες μέρες πριν. Είναι λίγο λιγότερο γνωστό ότι οι άνθρωποι που στήνουν αυτούς τους αγώνες (και ως εκ τούτου γνωρίζουν τον νικητή) το κάνουν σε μια μυστική συνάντηση και ξεκινούν να διαδίδουν τις πληροφορίες στην πόλη την μέρα μετά την συνάντηση.

Την πρώτη μέρα μετά τη συνάντηση, όλοι οι άνθρωποι που γνωρίζουν τις πληροφορίες για τον νικητή αρχίζουν να μοιράζονται αυτές τις πληροφορίες με όλους τους ανθρώπους που ζουν το πολύ ~K~ βήματα μακριά από τα σπίτια τους.

Τη δεύτερη μέρα μετά τη συνάντηση, όλα τα άτομα που γνωρίζουν τις πληροφορίες για τον νικητή αρχίζουν να μοιράζονται αυτές τις πληροφορίες με όλους τους ανθρώπους που ζουν το πολύ ~2 \cdot K~ βήματα μακριά από το σπίτι τους.

Γενικά, τη ~X~-ιοστή μέρα μετά τη συνάντηση, ξεκινούν όλοι όσοι γνωρίζουν τις πληροφορίες για τον νικητή, κοινοποίηση αυτών των πληροφοριών με όλους τους ανθρώπους που ζουν το πολύ ~X \cdot K~ βήματα μακριά από το σπίτι τους.

Μπορούμε να αναπαραστήσουμε το Μπέρμιγχαμ ως γράφημα όπου οι κόμβοι αντιπροσωπεύουν τα σπίτια και οι ακμές αντιπροσωπεύουν αμφίδρομους δρόμους που συνδέουν αυτά τα σπίτια.Τα σπίτια ευρετηριάζονται με αυξανόμενους ακέραιους αριθμούς από το 1 στο ~N~ και λέμε ότι ένα άτομο μπορεί να διανύσει κάθε δρόμο με ένα μόνο βήμα. Είναι δυνατό να φτάσει κανείς ένα σπίτι διασχίζοντας μια ακολουθία από δρόμους.

Το καθήκον σας είναι να καθορίσετε, για κάθε σπίτι, ποια ημέρα θα το φτάσουν οι πληροφορίες για τον νικητή του αγώνα.

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις ακέραιους ~N,\;M,\;Q~ και ~K\;(1 \le N,\;Q,\;K \le 100\,000,\;Q \le N,\;1 \le M \le 200\,000)~, ο αριθμός των σπιτιών στο Μπέρμιγχαμ, ο αριθμός των δρόμων στο Μπέρμιγχαμ, ο αριθμός των ανθρώπων που ήταν παρόντες στη μυστική συνάντηση και ο αριθμός Κ από την περιγραφή της εργασίας.

Η επόμενη γραμμή περιέχει ~Q~ ακέραιους όπου ο i-οστός ακέραιος αντιπροσωπεύει τον δείκτη ενός σπιτιού όπου το i-οστό άτομο από τη μυστική συνάντηση ζει μέσα.

Η i-οστή των επόμενων ~M~ γραμμών περιέχει ακέραιους ~A_i~ και ~B_i\;(1 \le A_i,\;B_i \le N,\;A_i \ne B_i)~, που δηλώνουν ότι ο i-οστός δρόμος συνδέει σπίτια με δείκτες ~A_i~ και ~B_i~.

Έξοδος

Έξοδος ~N~ αριθμών όπου ο i-οστός αριθμός αντιπροσωπεύει ποια ημέρα μετά τη συνάντηση το άτομο που μένει στο σπίτι με δείκτη ~i~ θα ανακαλύψει ποιος θα κερδίσει τον αγώνα.

Βαθμολογία

Στις περιπτώσεις δοκιμής συνολικής αξίας 20 βαθμών, θα ισχύει ~K = 1,\;1 \le N, Q \le 100~ και ~1 \le M \le 200~.
Στις περιπτώσεις δοκιμής αξίας επιπλέον 15 πόντων, θα ισχύει ~1 \le N, Q \le 100~ και ~1 \le M \le 200~.

Παραδείγματα

input

6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

output

1 1 2 2 1 0

input

6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

output

1 1 1 0 1 0

input

6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

output

1 1 1 2 1 0

Εξήγηση του 3ου παραδείγματος:

Το σχήμα αντιπροσωπεύει ένα γράφημα από το τρίτο παράδειγμα.Τα σπίτια 1, 2, 3 και 5 είναι το πολύ δύο βήματα μακριά από το σπίτι 6, οι άνθρωποι που μένουν σε αυτά θα μάθουν για τον νικητή την επομένη της συνάντησης. Το άτομο που μένει στο σπίτι 4 θα μάθει για τον νικητή δύο ημέρες μετά τη συνάντηση.