고양이 투어

자그레브에는 공원 $n$개, 고양이 $m$마리, 공원을 잇는 길 $n + m$개가 있다. 고양이는 영역 의식이 강해서 길마다 고양이가 최대 한 마리만 있다. 고양이는 길의 한 방향으로 지나가는 사람을 공격하고, 반대 방향으로 지나가는 사람에게는 쓰다듬어 달라고 요구한 뒤에야 통과시킨다. 자그레브시는 이 점을 알고, 고양이가 없는 길 $n$개만으로 어느 공원에서든 다른 모든 공원에 갈 수 있도록 길을 정비했다.

관광 센터는 자그레브에서 고양이 투어를 열기로 했다. 투어는 한 공원에서 출발해 자그레브의 모든 고양이를 쓰다듬고 출발한 공원으로 돌아온다. 관광객이 길을 잃지 않도록 센터는 각 길마다 다음에 갈 길을 알려주는 표지판을 세운다. 따라서 투어는 같은 길을 두 번 지날 수 없으며, 반대 방향으로 지나는 것도 안 된다. 관광객은 모든 고양이를 빠짐없이 쓰다듬고, 어떤 고양이에게도 공격받지 않으며, 투어가 가능한 한 짧기를 바란다.

가장 짧은 고양이 투어의 길이를 구하라. 투어가 불가능하면 그렇다고 답하라.

첫 줄에 정수 $n$, $m$ ($1 \le n \le 2 \cdot 10^4$, $0 \le m \le 2 \cdot 10^4$)이 주어진다. 각각 공원의 수와 고양이의 수이다.

이어지는 $n$개의 줄에는 고양이가 없는 길을 나타내는 쌍 $a$, $b$ ($1 \le a, b \le n$)가 주어진다. 한 공원에서 자기 자신으로 이어지는 길이나, 같은 두 공원을 잇는 길이 여러 개일 수 있다.

이어지는 $m$개의 줄에는 고양이가 있는 길을 나타내는 쌍 $x$, $y$ ($1 \le x, y \le n$)가 주어진다. 이 길의 고양이는 $x$에서 $y$로 가는 통행만 허용한다. 같은 두 공원을 잇는 길이 여러 개일 수 있다.

가장 짧은 고양이 투어의 길이를 한 줄에 출력한다. 고양이 투어가 존재하지 않으면 $-1$을 출력한다.

첫 번째 예제에서 가장 짧은 고양이 투어는 3 → 5 → 3이다.