[USACO05OPEN] Around the world G

Luogu

IDLGP9834

Time350ms

Memory64MB

DifficultyP4

2005USACO

这些年，农夫约翰在国际上交了一大批开农场的朋友。由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去拜访他们。他知道每个朋友的农场的经度（是一个从 $0$ 到 $359$ 的整数，我们把地球看成一个圆，经度在此圆上顺时针方向递增）。农夫约翰打算乘飞机去拜访他的 $n$ 个朋友（用 $1$ 到 $n$ 来表示）。他知道在这些农场之间有 $m$ 条双向的航线。飞机是沿着地面上最短的路径飞行的（就是圆上的最短弧长）。两个农场之间的航线一定是最短的。保证如果有两个农场在直径两端，那么它们之间一定不会被某条航线直接连接。所以任何一次航行都可以被描述成顺时针或是逆时针的．比如说，经度 $30$ 到经度 $35$ 是顺时针的，经度 $350$ 到经度 $10$ 也是顺时针的，而经度 $350$ 到经度 $200$ 是逆时针的。农夫约翰为了耍酷，决定要经过几个朋友的农场做到环球旅行，他想知道这是否可能，如果可能最少要乘几次飞机。他想在他最好的朋友（即输入中的第一个）的农场上开始和结束这次旅行。为了保证这是一次环球航行，结束旅行，顺时针经过的路程不能等于逆时针经过的路程。 ## Input 第一行两个用空格隔开的整数 $n$ 和 $m$。第二到 $n+1$ 行：第 $i+1$ 行有一个整数，表示第 $i$ 个农场的经度。第二行是他的最好的朋友的地址。第 $n+2$ 过程 $n+m+1$ 行：第 $i+n+1$ 行有两个整数，表示这两个农场之间有航线。 ## Output 一个整数，表示农夫约翰至少要乘几次飞机才能完成环球旅行。每次农夫约翰从一个农场前往另一个农场算作乘一次飞机。如果不可能做到环球旅行则输出 `-1`。 [samples] ## Note 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^3$，$1 \leq m \leq 2.5 \times 10^4$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[USACO05OPEN] Around the world G",
    "description": {
      "content": "这些年，农夫约翰在国际上交了一大批开农场的朋友。由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去拜访他们。 他知道每个朋友的农场的经度（是一个从 $0$ 到 $359$ 的整数，我们把地球看成一个圆，经度在此圆上顺时针方向递增）。   农夫约翰打算乘飞机去拜访他的 $n$ 个朋友（用 $1$ 到 $n$ 来表示）。他知道在这些农场之间有 $m$ 条双向的航线。飞机是沿着地面",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 350,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9834"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这些年，农夫约翰在国际上交了一大批开农场的朋友。由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去拜访他们。\n\n他知道每个朋友的农场的经度（是一个从 $0$ 到 $359$ 的整数，我们把地球看成一个圆，经度在此圆上顺时针方向递增）。  \n\n农夫约翰打算乘飞机去拜访他的 $n$ 个朋友（用 $1$ 到 $n$ 来表示）。他知道在这些农场之间有 $m$ 条双向的航线。飞机是沿着地面...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments