505B.md (2278B)
1 Source: https://codeforces.com/problemset/problem/505/B 2 3 B. Mr. Kitayuta's Colorful Graph 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Mr. Kitayuta has just bought an undirected graph consisting of *n* vertices and *m* edges. The vertices of the graph are numbered from 1 to *n*. Each edge, namely edge *i*, has a color *c**i*, connecting vertex *a**i* and *b**i*. 22 23 Mr. Kitayuta wants you to process the following *q* queries. 24 25 In the *i*-th query, he gives you two integers — *u**i* and *v**i*. 26 27 Find the number of the colors that satisfy the following condition: the edges of that color connect vertex *u**i* and vertex *v**i* directly or indirectly. 28 29 Input 30 31 The first line of the input contains space-separated two integers — *n* and *m* (2 ≤ *n* ≤ 100, 1 ≤ *m* ≤ 100), denoting the number of the vertices and the number of the edges, respectively. 32 33 The next *m* lines contain space-separated three integers — *a**i*, *b**i* (1 ≤ *a**i* < *b**i* ≤ *n*) and *c**i* (1 ≤ *c**i* ≤ *m*). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if *i* ≠ *j*, (*a**i*, *b**i*, *c**i*) ≠ (*a**j*, *b**j*, *c**j*). 34 35 The next line contains a integer — *q* (1 ≤ *q* ≤ 100), denoting the number of the queries. 36 37 Then follows *q* lines, containing space-separated two integers — *u**i* and *v**i* (1 ≤ *u**i*, *v**i* ≤ *n*). It is guaranteed that *u**i* ≠ *v**i*. 38 39 Output 40 41 For each query, print the answer in a separate line. 42 43 Examples 44 45 Input 46 47 ``` 48 4 5 49 1 2 1 50 1 2 2 51 2 3 1 52 2 3 3 53 2 4 3 54 3 55 1 2 56 3 4 57 1 4 58 ``` 59 60 Output 61 62 ``` 63 2 64 1 65 0 66 ``` 67 68 Input 69 70 ``` 71 5 7 72 1 5 1 73 2 5 1 74 3 5 1 75 4 5 1 76 1 2 2 77 2 3 2 78 3 4 2 79 5 80 1 5 81 5 1 82 2 5 83 1 5 84 1 4 85 ``` 86 87 Output 88 89 ``` 90 1 91 1 92 1 93 1 94 2 95 ``` 96 97 Note 98 99 Let's consider the first sample. 100 101  The figure above shows the first sample. 102 103 * Vertex 1 and vertex 2 are connected by color 1 and 2. 104 * Vertex 3 and vertex 4 are connected by color 3. 105 * Vertex 1 and vertex 4 are not connected by any single color.