Tidegate Bridge Path Problem

Tidegate Bridge Path Problem — ExecCode Hard DSA Practice

Solve the Tidegate Bridge Path problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Problem Statement There are N gates and M undirected cables. A cable is critical if cutting it splits the network into more pieces. You get Q queries. Each query is two gates U and V. Print how many critical cables you must cross when you walk from U to V without going around a cycle. Print 0 if: U and V are the same gate they still reach each other after every critical cable is removed they are in different connected components Gates are numbered from 1. Parallel cables are allowed. Input Format Cables come first. Queries come after. Output Format One integer per query. Constraints Example 1 Input The network is a path: 1—2—3—4. Three queries: 1 to 4 crosses 3 cables 2 to 3 crosses 1 cable 1 to 1 crosses 0 cables Output Example 2 Input A path of two cables. Query 1 to 3. Output Example 3 Input One cable. One query. Output

Examples

Input 4 3 3 1 2 2 3 3 4 1 4 2 3 1 1; Output 3 1 Input 3 2 1 1 2 2 3 1 3; Output 2. Input 2 1 1 1 2 1 2; Output 1

Constraints

1 ≤ N ≤ 2000, 0 ≤ M ≤ 3000, 1 ≤ Q ≤ 2000.

Practice Tidegate Bridge Path free on ExecCode. Browse DSA problems, topic map, and placement guides.