Earliest Activation Times

In a social network consisting of N users, some users are connected by friendship relations, and interactions occur among them over time. Each friendship is represented by an undirected edge between two users. Interactions occur at specific times and involve two users, which causes each user to become active if they were not active already.

Given the number of users N, the number of friendships M, and the number of interactions K, along with the list of friendships and interactions, determine the earliest time each user became active. If a user never became active through any interaction, output -1 for that user.

The activation follows the simple rule:

\(\text{activation_time}[u] = \begin{cases} t, & \text{if the user } u \text{ had an interaction at time } t \text{ and was inactive before}\\ -1, & \text{if the user never had an interaction} \end{cases}\)

inputFormat

The input is given from stdin in the following format:

N M K
u1 v1
u2 v2
... (M lines of friendships)
T1 u1 v1
T2 u2 v2
... (K lines of interactions)

Here, the first line contains three space-separated integers: N (number of users), M (number of friendships), and K (number of interactions).

The following M lines each contain two integers representing a friendship between two users.

The next K lines each contain three integers, where the first integer is the time of the interaction and the next two integers are the user IDs involved in that interaction.

outputFormat

Output one line to stdout: a list of N space-separated integers. The i^th integer should be the earliest time at which user i became active. If the user was never activated, output -1 for that user.

## sample

5 4 3
1 2
1 3
3 4
2 5
1 1 2
2 1 3
3 3 4

1 1 2 3 -1

</p>