270 . 小風愛仙人掌
TopCoder
Tags
Description
小風除了喜歡樹以外他也喜歡仙人掌。
因為小風怕大家不知道仙人掌的定義，所以他決定在者裡跟你講一下> <
仙人掌：若無向連通圖 $G$ 的任意一條邊最多出現在一條簡單迴路上，則圖 $G$ 為一個仙人掌圖。
他喜歡比較高的仙人掌，可是他不太清楚要怎麼估計仙人掌的高度，於是他決定給你 $Q$ 筆詢問，每筆詢問給定兩點 $s_i$, $t_i$，求 $s_i$ 走到 $t_i$ 的最長簡單路徑。
其中簡單路徑指的是頂點皆不重複的路徑。
Input Format
第一行給定兩個整數 $N, M$。
接下來 $M$ 行每行給定兩個點 $u_i, v_i$，代表 $u_i$ 與 $v_i$ 有邊相連。
下一行有一個整數 $Q$。
接下來 $Q$ 行每行給定兩個整數 $s_i, t_i$，代表詢問 $s_i$ 走到 $t_i$ 的最長簡單路徑
- $1 \leq N$, $M, Q \leq 3 \times 10^ 5$
- $1 \leq u_i, v_i, s_i, t_i \leq$ $N$
- 保證輸入的圖為仙人掌
Output Format
輸出 $Q$ 行，第 $i$ 行有一個整數，代表 $s_i$ 走到 $t_i$ 的最長簡單路徑，若不存在簡單路徑則輸出 0。
Sample Input 1
8 9
1 5
5 8
1 8
5 6
5 6
1 2
1 3
1 4
1 7
5
2 1
5 5
1 5
1 3
1 3
1 5
5 8
1 8
5 6
5 6
1 2
1 3
1 4
1 7
5
2 1
5 5
1 5
1 3
1 3
Sample Output 1
1
0
2
1
1
0
2
1
1
Hints
Problem Source
IOICamp 2020 Day5 pG
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~30 | 無額外限制 | 100 |