Earliest Time All Users Are Connected

A log entry time u v means u and v are connected from that moment on, and connections are transitive. Return the time when all given users first belong to the same connected component; if they can never all be connected, output −1. A single user is already connected before any log entry occurs, and this site defines the output as 0 in that case.

This site has made the standard input and output explicit.

输入格式

The first line contains n m, followed by n distinct usernames, then m lines of time u v. On this site 1≤n≤100000, 0≤m≤200000, usernames are 1..20 ASCII letters, digits or underscores, 0≤time≤10⁹, and every user in the logs exists.

输出格式

Output one integer, the answer.

样例 1

输入：

3 3
a b c
3 a b
7 b c
9 a c

输出：

7

样例 2

输入：

1 0
alone

输出：

0

样例 3

输入：

2 0
a b

输出：

-1

样例说明

Example 1: at time 3 only a and b are connected; c joins at time 7, so output 7. Example 2: a single user needs no connection, so output 0. Example 3: there are no logs, so the two users can never be connected; output −1.