题目描述

平面上有 $n$ 个顶点，部分顶点之间存在双向道路。道路长度为两个端点的欧几里得距离。给定起点 $s$ 和终点 $t$，请输出一条最短路径。

输入格式

第一行一个整数 $n$。接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个顶点的坐标。接下来一行一个整数 $m$，然后 $m$ 行，每行两个顶点编号，表示一条双向道路。最后一行两个整数 $s,t$。

输出格式

输出路径上的顶点编号，使用 --> 连接。例如 1-->2-->5。

如果存在多条最短路径，输出任意一条即可。起点与终点相同时，只输出这个顶点编号。路径不能重复经过顶点。

样例

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

1-->2-->5

数据范围

• $1\le n\le100$，$0\le m\le n(n-1)/2$。
• $-10000\le x_i,y_i\le10000$。
• 顶点编号在 $1$ 到 $n$ 之间，道路没有自环和重边。
• 保证起点可以到达终点。