| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 3 | 1 | 1 | 33.333% |
Because of all the travelling around the country for IATI 2022, the tour guide company of Kyusho was once again overwhelmed with questions. The region, for which his company is responsible, consists of $N$ cities, numbered from 1ドル$ to $N$. Between them, there are $M$ direct roads, numbered from 1ドル$ to $M,ドル each connecting a pair of different cities. There may be more than one direct road in a given direction between two cities.
The dispatch department frequently receives questions from the bus drivers which are of the following type: "Can you always go from city $A$ to city $B$ and then go back to city $A$ even if one of the roads is closed?".
Kyusho knows that you’re an experienced programmer so he asks you to write a program connect that answers the incoming questions of the described type.
The first line of the standard input contains two positive integers: $N$ – the number of cities and $M$ – the number of direct roads in the region.
Each of the next $M$ lines contains two positive integers $A$ and $B,ドル which specify that there is a direct road from city $A$ to city $B$.
The next line contains the positive integer $Q$ – the number of questions. Each of the following $Q$ lines contains two positive integers $A$ and $B,ドル describing a question from a driver, asking about cities $A$ and $B$.
Note that sometimes the questions are so many that Kyusho thinks it‘s best to get the answers for each unordered pair of cities $(A, B)$. For convenience, when $Q = 0$ it will imply that we are in that case. Then the questions $(1,1)$; $(1,2)$; $(1,3)$; $\dots$; $(1,N)$; $(2,2)$; $(2 ,3)$; $\dots$; $(2,N)$; $(3,3)$; $\dots$; $(3,N)$; $\dots$; $(N,N)$; have to be answered in that order.
For each question we will assign a number in the following way:
Let the resulting numbers for the questions are: $s_1, s_2, s_3, \dots , s_K,ドル where $K = Q$ if $Q \ne 0$ and $K = (N \times (N + 1)) / 2$ if $Q = 0$. Then on a single line of the standard output print the remainder of the number $P = s_1 \times B^{K-1} + s2 \times B^{K-2} + s_3 \times B^{K-3} + \cdots + s_K \times B^0$ modulo 10ドル^9 + 7$ where $B = 2 \times 10^5$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 13 | $N \le 200,ドル $M \le 1000,ドル $Q \le 500,ドル $Q \ne 0$ |
| 2 | 19 | $N \le 2000,ドル $M \le 10^5,ドル $Q \le 10^5,ドル The answer to each question is either 0ドル,ドル or $M+1$ |
| 3 | 10 | $N \le 500,ドル $M \le 8000,ドル $Q \le 10^5$ |
| 4 | 12 | $N \le 2000,ドル $M \le 10^5,ドル $Q \le 10^4,ドル $Q \ne 0,ドル There exists a direct road between cities $p$ and $p+1$ in both directions for all 1ドル ≤ p ≤ N - 1$ |
| 5 | 25 | $N \le 2000,ドル $M \le 10^5,ドル $Q \le 10^4,ドル $Q \ne 0$ |
| 6 | 10 | $N \le 2000,ドル $M \le 8000,ドル $Q \le 10^5$ |
| 7 | 11 | $N \le 2000,ドル $M \le 10^5,ドル $Q \le 10^5$ |
6 11 1 4 4 3 3 5 5 1 1 3 3 6 5 6 6 2 4 2 5 1 3 5 0
575589257
Question for $(1,6)$: There is no route from city 6ドル$ to city 1ドル$ even without closing one of the direct roads.
Question for $(1,3)$: No matter which road is closed, there are routes in both directions between the cities.
Question for $(4,5)$: If the road from city 1ドル$ to city 4ドル$ is closed, there will be no route from city 5ドル$ to city 4ドル$.
The assigned numbers to the questions are: 12ドル$ 0ドル$ 12ドル$ 1ドル$ 12ドル$ 0ドル$ 12ドル$ 0ドル$ 0ドル$ 0ドル$ 0ドル$ 12ドル$ 1ドル$ 12ドル$ 0ドル$ 12ドル$ 1ドル$ 0ドル$ 12ドル$ 0ドル$ 12ドル$
8 17 5 2 6 5 4 6 4 8 4 3 3 1 2 7 7 4 5 4 8 7 8 3 3 6 6 1 2 4 1 5 1 5 5 2 4 4 6 8 1 5 2 6 7
995598902
Question for $(8,1)$: If the road from city 4ドル$ to city 8ドル$ is closed, there will be no route from city 1ドル$ to city 8ドル$.
Question for $(6,7)$: If the road from city 7ドル$ to city 4ドル$ is closed, there will be no route from city 7ドル$ to city 6ドル$.
The assigned numbers to the calls: 18ドル$ 4ドル$ 18ドル$ 8ドル$