Subway Ride

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Being a newcomer to Computopia, Chef is confused by the countless subway lines in the city. Help him! You are given an undirected graph with $N$ vertices and $M$ edges. There are no selfloops and no simple cycles that contain more than 2 edges in the graph (i.e. if we replaced each set of multiple edges connecting the same pair of vertices by one edge, we would obtain a tree). Each edge also has a colour. Consider a simple path with length $K$ in the graph that passes through edges with colours $A_1, A_2, \dots, A_K$ in this order. The *cost* of this path is defined as $(A_1 \neq A_2) + (A_2 \neq A_3) + \dots + (A_{K1} \neq A_K)$, where the boolean value `true` is interpreted as the integer $1$ and `false` is interpreted as $0$. In other words, the cost of a simple path is the number of pairs of neighbouring (consecutive) edges on this path with different colours. The cost of a path with length $0$ is defined to be $0$. You need to answer $Q$ queries. In each query, you are given vertices $u$ and $v$; you should find the maximum possible cost of some simple path connecting them. Note that a simple path may not visit a vertex more than once. ### Input  The first line of the input contains two spaceseparated integers $N$ and $M$.  Each of the next $M$ lines contains three spaceseparated integers $u$, $v$ and $w$ denoting an edge between vertices $u$ and $v$ with colour $w$.  The next line contains an integer $Q$.  Each of the next $Q$ lines contains two spaceseparated integers $u$ and $v$ describing a query. ### Output For each query, print a single line containing one integer — the maximum cost of a simple path. ### Constraints  $1 \le N, Q \le 500,000$  $1 \le M \le 1,000,000$  $1 \le u, v \le N$  for each edge, $u \neq v$  $1 \le w \le M$ ### Subtasks **Subtask #1 (20 points):**  $1 \le N, Q \le 10$  $1 \le M \le 100$ **Subtask #2 (20 points):**  $1 \le N, Q \le 500$  $1 \le M \le 10,000$ **Subtask #3 (20 points):**  $1 \le N, Q \le 5,000$  $1 \le M \le 100,000$ **Subtask #4 (20 points):**  $1 \le N, Q \le 100,000$  $1 \le M \le 300,000$ **Subtask #5 (20 points):** original constraints ### Example Input ``` 8 10 1 2 1 1 2 2 1 3 2 1 3 3 2 4 2 2 5 1 3 6 3 3 7 1 3 8 1 3 8 3 5 2 3 5 6 4 6 4 8 4 7 ``` ### Example Output ``` 1 2 3 3 3 ```Author:  lzr010506 
Editorial  https://discuss.codechef.com/problems/SUBWAY 
Tags  july18, lzr010506, mediumhard 
Date Added:  28062018 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions