시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 (추가 시간 없음) 1024 MB138758.333%

문제

In medieval times, keeping track of the relationships between cities was extremely difficult, since most cities did not have access to the internet[citation needed]. However, it was possible to determine whether two cities were friendly with each other by examining their coats of arms. In those days, every coat of arms showed two symbols: one at the top, and one at the bottom. If two cities have an equal symbol at the top or they have an equal symbol at the bottom, they are friendly.

Following the saying "the friends of my friends are my friends", two cities $c_0$ and $c_f$ can be indirectly friendly if there exist cities $c_1, \ldots, c_{f-1}$ such that $c_k$ is friendly with $c_{k+1}$ for $0\leq k < f$. If $c_0$ and $c_f$ are different and indirectly friendly, then we say that the friendship degree of these cities is the smallest possible $f$ following this definition. See Figure B.1 for an example.

Parts of these coats of arms are CC BY-SA 4.0 on Wikimedia Commons.

Figure B.1: Illustration of Sample Input 1. Cities $1$ and $2$ are directly friendly, as well as cities $2$ and $3$. Cities $1$ and $3$ have a friendship degree of $2$, because they are indirectly friendly via city $2$. City $4$ is not (indirectly) friendly with any other city.

You are given a list of coats of arms and a list of queries. For every query, determine the friendship degree of the two given cities.

입력

The input consists of:

  • One line with two integers $n$ and $s$ ($2\leq n\leq 90\,000$, $2\leq s\leq 300$), the number of cities and the number of symbols that may appear on the coat of arms of some city.
  • $n$ lines, the $i$th of which consists of two integers $t_i$ and $b_i$ ($1\leq t_i, b_i\leq s$). $t_i$ is the symbol on the top side of the coat of arms of the $i$th city, and $b_i$ is the symbol on the bottom side of the coat of arms of the $i$th city. If $i\neq j$, then $t_i\neq t_j$ or $b_i\neq b_j$.
  • One line with an integer $q$ ($1\leq q\leq 10^5$), the number of queries.
  • $q$ lines, the $i$th of which contains two integers $c$ and $d$ ($1\leq c, d\leq n$, $c\neq d$), two cities for which you should calculate the friendship degree.

출력

For every query, output an integer stating the friendship degree of the two cities, or $-1$ if the two cities are not (indirectly) friendly.

예제 입력 1

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

예제 출력 1

1
1
2
-1

예제 입력 2

7 5
1 1
2 1
2 2
3 2
4 2
3 5
3 4
6
1 2
1 3
1 7
1 4
1 5
6 7

예제 출력 2

1
2
4
3
3
1

예제 입력 3

2 4
1 2
3 4
1
1 2

예제 출력 3

-1

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2022 연습 세션 PB번

  • 문제를 만든 사람: Markus Himmel