时空限制

1S/512M

题目描述

某大型铁路公司运营着两个不同类型的轨道网络，覆盖了 $n$ 个城市，编号为 $1$ 到 $n$。

• A 类轨道网络：包含 $m_1$ 条双向轨道，连接若干城市对 $(u, v)$。
• B 类轨道网络：包含 $m_2$ 条双向轨道，连接若干城市对 $(u, v)$。

公司规定：旅客从城市 $1$ 出发前往城市 $n$ 时，一开始可以先选择其中一类轨道乘坐，但在整个行程中最多只允许进行一次换乘（即从 A 类轨道换乘到 B 类轨道，或从 B 类轨道换乘到 A 类轨道）。如果旅客全程只乘坐一种类型的轨道，也视为符合条件。

假设每条轨道连接两座城市的长度均为 $1$。请你计算旅客从城市 $1$ 到城市 $n$ 所需的最短行程长度。如果无法到达，请输出 -1。

格式

输入格式

第一行包含三个整数 $n, m_1, m_2$ ($2 \le n \le 2 \times 10^5, 0 \le m_1, m_2 \le 2 \times 10^5$)。

接下来 $m_1$ 行，每行包含两个整数 $u, v$，表示有一条 $u,v$ 之间的 A 类轨道。

接下来 $m_2$ 行，每行包含两个整数 $u, v$，表示有一条 $u,v$ 之间的 B 类轨道。

输出格式

输出一个整数，表示满足条件的最短路径长度。若不存在，输出 -1。

样例

样例输入 #1

3 1 1
1 2
2 3

样例输出 #1

2

样例解释 #1

旅客从城市 $1$ 乘坐 A 类轨道到达城市 $2$，随后在城市 $2$ 换乘 B 类轨道到达城市 $3$，总长度为 $2$，换乘次数为 $1$，符合规定。

样例输入 #2

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

样例输出 #2

4

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$0 \le m_1, m_2 \le 2 \times 10^5$。